For what positive integers $k$ does there exist a positive integer $n$ such that $n^k+k$ is a perfect square?
Certainly for all $k$ such that $k+1$ is a perfect square, since we can substitute $n=1$.
For $k=2$, we have that $n^2+2$ is a perfect square, but modulo $4$ this cannot occur. For other even values of $k$, we get that two perfect squares must differ by $k$, which restricts the possibility to just $n=1$, and we covered that in the previous paragraph.
So the hard case remains with odd values of $k$.