Assume $2^n+m=a^2$ with $a,m,n\in\mathbb N$, $0.
If $n=2k$ is even, then $(2^k)^2=2^n and $(2^k+1)^2=2^n+2\cdot 2^k+1>2^n+m$, contradiction.
If $n=2k+1$ is odd, then $\left(\frac a{2^k}\right)^2=2+\frac m{2^{2k}}$, i.e. $\frac a{2^k}$ is a relatively good approximation for $\sqrt 2$. In fact with $\frac a{2^k}>\sqrt 2$ we find that $\frac m{2^{2k}}=\left(\frac a{2^k}\right)^2-2=\left(\frac a{2^k}+\sqrt2\right)\left(\frac a{2^k}-\sqrt2\right)>2\sqrt 2 \cdot\left(\frac a{2^k}-\sqrt2\right),$ hence $0<\frac a{2^k}-\sqrt2<\frac{m}{2^n\sqrt 2}\le \frac{\sqrt{2^n}}{2^n\sqrt 2}=\frac1{2^{k+1}}.$ Letting $a=\lceil2^k\sqrt 2\rceil$ will therefore lead to an instance of $2^n+m=a^2$ about 50% of the time. If we relax the restriction on $m$ to $m\le 2\cdot\sqrt{ 2^n}$, this rate will go up to 100%. For example $2^{59}+9092137 = 759250125^2$.