In case it’s of interest to anyone, there is a reasonable elementary way to attack the problem semi-systematically and arrive at Justin’s answer.
$2^s\equiv -1\pmod n$, so $2^{s+1}\equiv -2\pmod n$, and we’d like to find $m$ so that $m^2\equiv -2^{s+1} \pmod n$. Suppose that $m=a-1$; then $m^2=a^2-2a+1$, and it’s tempting to try $a=2^s$. Unfortunately, then $m^2=2^{2s}-2^{s+1}+1$, and $2^{2s}+1$ is not a multiple of $2^s+1$, so we have to work harder to get a $-2^{s+1}$ term.
The middle term of a square is still a reasonable place to look, and that means considering something of the form $(2^a-2^b)^2$, where $a+b=s$. In other words, we hope for an $a$ such that $(2^a-2^{s-a})^2=2^{2a}+2^{2(s-a)}-2^{s+1}=r(2^s+1)-2^{s+1}$ for some integer $r$. Clearly we may assume that $a>s-a$ and set $b=s-a$ and $c=a-b$, so that we want $2^{2b+2c}+2^{2b}=r(2^{2b+c}+1)$, or $2^{2b}(2^{2c}+1)=r(2^{2b+c}+1)$. Clearly this requires that $r=2^{2b}$ and $2b+c=2c$. From the latter we get $c=2b$, so, since $2b+c=s$, we must have $c=s/2$ and $b=s/4$, i.e., $c=2^{2^{k-1}}$ and $b=2^{2^{k-2}}$. (At this point the reason for the restriction to $k\ge 2$ becomes clear.) The desired square root is then $2^a-2^b=2^{b+c}-2^b=2^{3\cdot 2^{k-2}}-2^{2^{k-2}}=2^{2^{k-2}}\left(2^{2^{k-1}}-1\right)\;.$