Your use of Hensel's Lemma works fine, if $b$ is co-prime to $p$. Here is another approach:
Let me deduce the following result without using Hensel's Lemma, but only basic group theory and some element-counting.
Let $p$ be an odd prime and $b$ co-prime to $p$, let $n$ be any integer. Then $x^2=b \pmod {p^n}$ has two solutions of $b$ is a quadratic residue and zero solutions in the other case.
Proof:
$(\mathbb Z/p^n\mathbb Z)^*$ is a cyclic group of even order $N = p^{n-1}(p-1)$, hence it contains exactly one element of order $2$. Thus the kernel of the square map
$$(\mathbb Z/p^n\mathbb Z)^* \to (\mathbb Z/p^n\mathbb Z)^*, x \mapsto x^2$$
consists of two elements. This yields that the equation $x^2=b \pmod {p^n}$ has either two or zero solutions and precisely one half of all choices for $b$ belongs to either case.
Certainly, if $x^2=b \pmod p$ is not solvable, then $x^2=b \pmod {p^n}$ is not solvable for any $n$. Thus we have found $\frac{N}{2}$ choices for $b$ that yield no solutions (The quadratic non-residues). By our arguments above, we deduce that the other $\frac{N}{2}$ choices for $b$ must yield two solutions. These are precisely the quadratic residues modulo $p$.
Let us attack the general case, where $b=up^m$ with $0 \leq m < n$ and $u$ co-prime to $p$: Then you can easily show that $x^2=b \pmod {p^n}$ is solvable iff $x^2=u \pmod {p^n}$ is solvalbe and $m$ is even.
For simplicity, I am using x instead of $x_k$.
i.e. we know $x^2 \equiv a \pmod 2^k$
Case 2: m is odd.
Calculate $ {(x+ 2^{k-1})}^2 \bmod 2^{k+1}$
Expanding the LHS we get
LHS = $x^2 + 2*2^{k-1}*x + 2^{2k-2}$
$ = x^2 + x.2^k + 2^{2k-2}$
The 3rd term in the above evaluates to $0 \bmod 2^{k+1}$
So we have $x^2 + x.2^k \bmod 2^{k+1}$
$\frac {x^2 - a}{2^k} = m$
$x^2 = m.{2^{k}} + a$
So $x^2 + x.2^k \bmod 2^{k+1}$
$ = m.{2^{k}} + a + x.2^k \bmod 2^{k+1}$
$ = 2^k(m + x) + a \bmod 2^{k+1}$
$a\equiv1\bmod 8$, so a is odd.
$m$ is odd.
$x^2 = a + m.2^k$. Since $a$ & $m$ are odd, RHS here is odd & hence $x^2$ is odd & hence $x$ is odd
Since $m$ & $x$ are odd, $m+x$ is even & hence can be expressed as $2*n$
i.e. Let $m+x = 2n$
So we have
$2^k(m + x) + a \bmod 2^{k+1}$
$ = 2^k * 2n + a \bmod 2^{k+1}$
$ = 2^k * 2n + a \bmod 2^{k+1}$
$ = 2^{k+1} + a \bmod 2^{k+1}$
$ = a \bmod 2^{k+1}$
Which is what we set out to prove
${(x+2^{k-1})}^2 \equiv a \pmod {2^{k+1}}$
So it's proven for both cases - when m is odd or even.
A big thank you to GerryMyerson for guiding me through this.
Best Answer
We give a counting argument. Let $p$ be an odd prime, and suppose that $a$ is not divisible by $p$. Then the congruence $x^2\equiv a\pmod{p^k}$ has either no solution or two solutions.
To prove this, suppose $b^2\equiv a\pmod{p}$. Then from $x^2\equiv b^2\pmod{p^k}$ we conclude that $p^k$ divides $(x-b)(x+b)$. Since $p$ cannot divide both, we conclude that $p^k$ divides one of $x-b$ or $x+b$. So if the congruence has at least one solution $b$, it has exactly two, namely $b$ and $-b$.
The function $f(x)=x^2$ (modulo $p^k$) maps the set $H$ of numbers between $1$ and $p^k-1$ that are not divisible by $p$ to $H$. By the above, this function is two to one.
So half of the elements of $H$ are QR of $p^k$, and half are not. Which half? The ones congruent to a quadratic residue modulo $p$. For if $a$ is not a square modulo $p$, it cannot be a square modulo $p^k$.
The above argument proves that for odd primes $p$, every quadratic residue modulo $p$ is a quadratic residue modulo $p^k$. The result does not hold for $p=2$: Note that $3$ is a quadratic residue of $2$ but not of $4$.