Может ли существовать многочлен от одной переменной...

Вообще, кажется, есть теорема о том, что всякий многочлен от одной переменной с целыми коэффициентами P(x), который для целых значений x выдаёт только простые числа, является константой.

Конкретно на твой вопрос можно дать ответ даже проще.
Давай предположим, что мы нашли такой многочлен P(x), который выдаёт различные простые числа при подстановке натуральных значений x (даже необязательно последовательно).
Тогда P(1) — некоторое простое число, которое я обозначу p.
Рассмотрим теперь P(1 + mp), где m — целое число. Наш многочлен имеет вид
P(x) = Σaₖx^k, а соответственно P(1) = Σaₖ = p
При вычислении P(1 + mp) можно раскрыть степень (1 + mp)^k по биному (см. картинку) и убедиться в том, что все слагаемые с ненулевыми степенями (mp)^j делятся на p, а слагаемое с нулевой степенью — вообще равно Σaₖ = p
Итого мы показали, что для всех m число P(1 + mp) делится на p. А, стало быть, такого многочлена, как ты ищешь, не существует.

Пример для понимания: многочлен P(x) = 3x² - 7x + 11 принимает простое значение 7 при x = 1: P(1) = 7. Тогда, например,
P(1 + 3*7) = P(22) = 1309 = 187*7 — делится на 7

Нет. Иначе искать большие простые числа не имело бы смысла.

Степень многочлена должна быть = бесконечности. А для конечного отрезка ряда простых чисел легко построить, как интерполяционный многочлен Лагранжа (или Ньютона, - дело вкуса).