The following theorem was left as an exercise in K. Ireland and M. Rosen's A Classical Introduction to Modern Number Theory. The theorem is as follows:
Let $2^l$ be the highest power of 2 dividing $n$. Suppose that $a$ is odd and that $x^n \equiv a \mod 2^{2l + 1}$ is solvable. Then $x^n \equiv a \mod 2^e$ is solvable for all $e \geq 2l + 1$.
The text says that one begins by assuming that $x^n \equiv a \mod 2^m$ (for some $m \geq 2l + 1$) is solvable and that $x_{0}$ is a solution to the congruence. Then $x_{1} = x_{0} + b2^{m - l}$ satisfies $x_{1}^n \equiv a \mod 2^{m+1}$ for an appropriately chosen $b$.
I am particularly interested in the specific case when $n = 2$, so then $l = 1$ and we assume that $x^2 \equiv a \mod 2^m$ is solvable for some $m \geq 3$ with $x_{0}$ a solution. If we let $x_{0}^2 - a = 2^m k$ for some $k \in \mathbb{Z}$ then (with $b$ still yet to be chosen) we have that $$x_{1}^2 - a = x_{0}^2 + 2^m b x_{0} + b^2 2^{2m - 2} - a = (x_{0}^2 - a) + 2^m b x_{0} + b^2 2^{2m - 2} = 2^m(k + bx_{0}) + b^2 \cdot 2^{2m - 2}$$
At this point I was hoping that it would be apparent how I should select $b$, but it still is not. Since $m \geq 3$, then $2m - 2 \geq m + 1$ and so $b^2 \cdot 2^{2m - 2} \equiv 0 \mod 2^{m + 1}$. Thus it suffices to have $k + bx_{0} = 2$ (or equal to some power of 2 greater than 2 itself).
I thought that selecting $b = 2x_{0} + k$ would work, however this leads to $$k + bx_{0} = k + (2x_{0} + k)x_{0} = k + 2x_{0}k + kx_{0}$$ and I still unable to factor out a 2 from the whole expression.
We work with your particular example, but the general argument is almost the same. As you wrote, we want to find $b$ such that $$x_1^2-a\equiv (x_0^2-a)+2^m bx_0\pmod{2^{m+1}},$$ or equivalently such that $$bx_02^m \equiv -(x_0^2-a)\pmod{2^{m+1}},$$ that is, $$bx_02^m \equiv -k2^m \pmod{2^{m+1}},$$ or equivalently $$bx_0\equiv -k\pmod{2}.$$ Note that we "cancelled" a $2^m$ from all the terms, including the modulus. More generally, we have $cx\equiv cy\pmod{cz}$ if and only if $x\equiv y\pmod{z}$. This is an immediate consequence of the definition of congruence.
Finally, since $x_0$ is odd, $bx_0\equiv -k\pmod{2}$ has a solution $b$.