Let $y$ be a prime such that $y^3 = 2^x + x^2 + 25$; clearly, $y$ is odd. Moreover, $x$ can not be a negative integer nor can it belong to the set $\{0, 1, 2, 3\}$. Hence $x \ge 4$ is even.

1. If $x = 6k$, with $k \in \mathbb{N}^*$, we get $64^k + 36k^2 + 25 = y^3$.

For $k=1$ we get $x=6$ and $y=5$.

For $k \ge 2$ we have no solutions because of the following inequalities:
$$(4^k)^3 < y^3 = 2^{6k} + (6k)^2 + 25 < (4^k + 1)^3,$$
the second inequality being equivalent with $3k^2 + 2 < 4^{k-1}(4^k + 1)$, which is true (induction).

2. If $x = 6k + 2$ or $x = 6k + 4$ then: $2^x \equiv 1 \pmod 3$, $x^2 \equiv 1 \pmod 3$ hence $2^x + x^2 + 25 \equiv 0 \pmod 3$, i.e. $y^3 \equiv 0 \pmod 3$, which means $y \equiv 0 \pmod 3$ and, as $y$ is prime, we get $y = 3$, which does not fulfill the condition.

In conclusion, the only solution is $x = 6$.