How to find all polynomials satisfying $P(x^2+x-4)=P^2(x)+P(x)$?

For $x=2$ the relation gives $\require{cancel}\,\bcancel{P(2)}=P^2(2)+\bcancel{P(2)}\,$, therefore $P(2)=0\,$. Assuming $P \not \equiv 0$, there must exist a multiplicity $n \ge 1$ and some polynomial $Q(x)$ such that $P(x)=(x-2)^n\cdot Q(x)$ and $Q(2) \ne 0$. Substituting back into the relation:

$$ \left(x^2+x-6\right)^n \cdot Q(x^2+x-4)=(x-2)^{2n} \cdot Q^2(x)+(x-2)^n \cdot Q(x) $$

Since $x^2+x-6=(x-2)(x+3)\,$:

$$ \bcancel{(x-2)^n} \cdot (x+3)^n \cdot Q(x^2+x-4)=\bcancel{(x-2)^n} \cdot (x-2)^n \cdot Q^2(x)+\bcancel{(x-2)^n} \cdot Q(x) \\[5px] \iff (x+3)^n \cdot Q(x^2+x-4)=(x-2)^n \cdot Q^2(x)+Q(x) $$

For $x=2\,$, the above reduces to $5^n \cdot Q(2) = Q(2)\,$, but the equality cannot hold for $n \ge 1$ and $Q(2) \ne 0\,$. Therefore, the only solution is the zero polynomial $P \equiv 0\,$.

The only polynomial with this property is the zero polynomial.

One can show by induction that $P^{(k)}(2) = 0$ for all $k \ge 0$, where $P^{(k)}$ is the $k$-th derivative. For $k = 0$, this is clear by the observation in the original post.

For the induction step, consider $\frac{d^{k+1}}{dx^{k+1}} P(s(x))$ where $s(x) = x^2 + x -4$. By Faa Di Bruno's Formula, this is of the form $$ \frac{d^{k+1}}{dx^{k+1}} P(s(x)) = P^{(k+1)}(s(x)) \times (s'(x))^{k+1} + \sum_{j=1}^k P^{(j)}(s(x)) g_j(x) $$
with suitable polynomials $g_j$. Setting $x = 2$ and thus $s(x) = 2$ and using the induction assumption, we obtain $P^{(k+1)}(2) \cdot (s'(2))^{k+1} = 5^{k+1}P^{(k+1)}(2)$.

The right hand side becomes by Leibniz' formula $$ \sum_{j=0}^{k+1} \binom{k+1}{j}P^{(j)}(z) P^{(k+1-j)}(z) + P^{(k+1)}(z) $$ For $z = 2$ this is just $P^{(k+1)}(2)$ since the products in the sum all vanish due to the induction assumption.

It follows that $$ 5^{k+1}P^{(k+1)}(2) = P^{(k+1)}(2) $$ and therefore $P^{(k+1)}(2)$ must vanish.

Therefore, $P$ vanishes to all orders at $z = 2$ and it must be identically equal to zero.