Sure, $n>-1$. Let $n>9$ and $2^n+n^2=m^2$ with $m>0$, so $2^n=(m-n)(m+n)$. Then $m-n=2^a$ and $m+n=2^b$ with $a+b=n$. Of course, $a<b \Rightarrow a \leq \frac{n-1}{2}, b \geq \frac{n+1}{2} \Rightarrow n=(2^b-2^a)/2 \geq (2^{(n+1)/2}-2^{(n-1)/2})/2=2^{(n-3)/2}$. But inequality $n \geq 2^{(n-3)/2}$ is false if $n>9$. Really, it's equivalent to $8n^2 \geq 2^n$. If $n=10$ we have $8 \cdot 100<1024$ and $2 \cdot 8n^2>8(n+1)^2$ if $n>9$. So, we proved our inequality by induction. Then for $n>9$ there is no solution. Now we need to check cases $n=0, 1,2,3,4,5,6,7,8,9$. But I'm lazy... (maybe, I will end later) Edit: if $2^n+n^2=f(n)$, then $f(0)=1$, $f(1)=3$, $f(2)=8$, $f(3)=17$, $f(4)=32$, $f(5)=57$, $f(6)=100$, $f(7)=177$, $f(8)=320$, $f(9)=593$. Hence, answer is $n=0$ and $n=6$.

official solution (in czech): https://www.matematickaolympiada.cz/media/3472047/a71iii.pdf#page=11

/bump...

Let $2^n + n^2 = k^2$ and $n = dn_0, k = dk_0$ with $gcd(n_0, k_0) = 1$ $\Longrightarrow 2^n = d^2(k_0 - n_0)(k_0 + n_0)$ $\Longrightarrow d \mid 2^n \Longrightarrow d = 2^i$ $\Longrightarrow 2^{n-2i} = (k_0 - n_0)(k_0 + n_0)$ But $k_0 - n_0$ and $k_0 + n_0$ have the same parity, so if $k_0 - n_0$ is odd $\Longrightarrow k_0 - n_0 = 1 = k_0 + n_0$ $\Longrightarrow n_0 = 0 \Longrightarrow n = 0. ABS!$ Then $k_0 - n_0$ and $k_0 + n_0$ are even, so, $k_0$ and $n_0$ are odd, now let $d_0 = mdc(k_0 - n_0, k_0 + n_0) $$\Longrightarrow d_0 \mid 2k_0 \Longrightarrow d_0 = 2$ Then, $2^{n-2i-2} = (\frac{k_0 - n_0}{2})(\frac{k_0 + n_0}{2})$, however $\frac{k_0 - n_0}{2}$ or $\frac{k_0 + n_0}{2}$ is odd $\Longleftrightarrow$ $\begin{cases} \frac{k_0 - n_0}{2} = 1 \\ \frac{k_0 + n_0}{2} = 2^{n-2i-2} \end{cases}$ $\Longrightarrow n_0 = 2^{n-2i-2} - 1 =$ $2^{2^in_0-2i-2} \geq 2^{n_0 - 2}$ but $2^{n_0-2} > n_0 \forall n_0 > 4$ (by induction) $\Longrightarrow n_0 \leq 4$ $\bullet$ $n_0 = 1$ $\Longrightarrow 1 = 2^{2^i-2i-2} - $$1 \Longrightarrow 2^i - 2i - 2 = 1$ It's easy to see that's fake. $\bullet$ $n_0 = 3$ $\Longrightarrow 3 = 2^{2^i\cdot 3-2i-2} - $$1 \Longrightarrow 2^i\cdot 3 - 2i - 2 = 2$ Hence, $i = 1 \Longrightarrow d = 2$ $\Longrightarrow n_0 = 6$ and $k_0 = 5$. $\therefore (n, k) = (6, 10).$