Suppose $\deg P \ge 2$.

Let $d = \deg P \ge 2$. Then for large $k$, $a_k$ grows very rapidly, since $a_k = P(a_{k-1})$ and $P$ is a degree $d$ polynomial with integer coefficients.

Let $b$ be any positive integer. By assumption, there exists $k$ such that $a_k = m^b$ for some integer $m > 1$.

Let us fix $n$ and consider the sequence $a_0, a_1, \ldots$. Since $P$ is a nonconstant integer polynomial, for large $k$, $a_k$ will be very large and will have many prime divisors (by Zsigmondy's theorem, for example, or by the fact that the sequence grows rapidly and is not eventually constant).

But for $a_k$ to be a perfect $b$-th power for every $b$, for every $b$ there must exist $k$ such that $a_k$ is a perfect $b$-th power. In particular, for $b$ large, $a_k$ must be a perfect $b$-th power, i.e., $a_k = m^b$ for some $m > 1$.

But for large $b$, the gap between consecutive perfect $b$-th powers grows very rapidly. For example, for $b = 100$, the numbers $2^{100}, 3^{100}, 4^{100}, \ldots$ are extremely far apart. Since $a_k$ grows rapidly, but $P$ is fixed, the sequence $a_k$ cannot hit perfect $b$-th powers for all $b$ unless $P$ is linear.

More precisely, for $d \ge 2$, $a_k$ grows as a tower of exponents, so for large $k$, $a_k$ is much larger than $(a_{k-1})^2$, and so on. The set of perfect $b$-th powers is very sparse for large $b$, so it is impossible for the sequence $a_k$ to hit a perfect $b$-th power for every $b$ unless $P$ is linear.

Now, suppose $\deg P = 1$, i.e., $P(x) = ax + b$ with $a, b \in \mathbb{Z}$, $a \ne 0$.

Then $a_k$ is an affine recurrence, so $a_k = a^k n + b \frac{a^k - 1}{a - 1}$ (if $a \ne 1$), which is an explicit formula. For suitable $n$, $a_k$ can be made to hit perfect $b$-th powers for all $b$ (for example, if $a = 1$, $P(x) = x + b$, then $a_k = n + k b$; for $a = -1$, $P(x) = -x + b$, $a_k$ alternates, but for suitable $n$ and $b$, $a_k$ can be a perfect $b$-th power).

Therefore, the only possibility is $\deg P = 1$.