A basic version of Hensel's Lemma states:
Suppose that $f(x) \in \mathbb{Z}[x]$, and integer $k \geq 2$, and $p$ is a prime, and $r$ is a solution of the congruence $f(x) \equiv 0 \mod p^{k-1}$. If $f'(r) \neq 0 \mod p$, then there is a unique integer $t$, $0 \leq t < p$, such that $f(r+tp^{k-1}) \equiv 0 \mod p^k$, given by
$$t \equiv -f'(r)^{-1} \cdot \frac{f(r)}{p^{k-1}} \mod p$$ where $f'(r)^{-1}$ is the inverse of $f'(r)$ modulo $p$.
Now consider $f(x) = x^{10}+x-10$. Solving this in $\mod 2$ yields $r \equiv 0$ as a solution. $f'(x) = 10x^9+1$. We see $f'(0) \equiv 1 \neq 0 \mod 2$. It follows, by the lemma, that $f(0 + 2t) \equiv 0 \mod 2^2$ must be a solution. Since $k=2$ in this case and $f(r)\equiv0 \mod 2$, it implies $t \equiv 0 \mod 2$. So $f(0) \equiv 0 \mod 4$. But plugging in $x=0$, we get $f(0) \equiv -10 \equiv 2 \mod 4$. So clearly $x=0$ is not a solution to $f(x) \equiv 0 \mod 4$. Have I applied the theorem wrong? I have checked my work multiple times and unfortunately, I have not found my mistake.
The iteration in Hensel's is not done correctly in your computation. You want to lift your solution to $\mathbb{Z}/4\mathbb{Z}$ so from $a_0=0$ you let $a_1=a_0+2b_1$, then $b_1$ will be given by $-a'_0/f'(a_0)\pmod{2}$ where $f(a_0)=a'_0\cdot 2$. In this case $f(a_0)=f(0)=-10=(-5)\cdot 2$, so that $b_1\equiv -5/1\equiv 1 \pmod{2}$, and so $b_1=1$, and your lifted solution is $a_1=2$. Indeed $2^{10}+2-10=1024+2-10=1016=254\cdot 2^2$. You can apply this same iteration to obtain higher approximations to a root in $\mathbb{Z}_2$.