If $p = q = 2$ we have $p^{q+1} + q^{p+1} = 2^3 + 2^3 = 16$, so that is one solution of the problem.

Now, without loss of generality assume that $p$ is odd and let $p^{q+1} + q^{p+1} = x^2$, where $x \in \mathbb{N}$. Thus $p+1$ is even and
$$p^{q+1} = \left(x - q^{\frac{p+1}{2}}\right) \left(x + q^{\frac{p+1}{2}}\right).$$
Denote the greatest common divisor of the two factors on the right-hand side by $d$. If $d > 1$ we have that $d$ is a power of $p$ and $d$ is also a factor of $2x$. It is easy to see that $p \mid q$, i.e. $p = q$. Thus $2p^{p+1} = x^2$, which is impossible.

Therefore $d = 1$, $x - q^{\frac{p+1}{2}} = 1$, $x + q^{\frac{p+1}{2}} = p^{q+1}$ and hence
$$2q^{\frac{p+1}{2}} = p^{q+1} - 1.$$
The above equation is impossible for $q$ odd because $2q^{\frac{p+1}{2}} \equiv 2 \pmod 4$ and $p^{q+1} - 1 \equiv 0 \pmod 4$. We conclude that $q = 2$ and
$$2^{\frac{p+3}{2}} = p^3 - 1 = (p-1)(p^2 + p + 1).$$
Since $\gcd(p-1, p^2 + p + 1) = 1$ we conclude that $p-1=1$, what is a contradiction.