Proceed by induction on $k$. Since $a \equiv 3 \pmod{8}$, $m = 1$ works for $k = 1, 2, 3$, so let $k \ge 3$ and let $m$ be a positive integer such that $a^m + a + 2$ is divisible by $2^k$.

If $(a^m + a + 2)/2^k$ is even, then $a^m + a + 2$ is clearly divisible by $2^{k+1}$.
If $(a^m + a + 2)/2^k$ is odd, we will show that $a^{m+2^{k-2}} + a + 2$ is divisible by $2^{k+1}$.
To this end, write $a^{m+2^{k-2}} + a + 2 = a^{2^{k-2}}(a^m + a + 2) - (a+2)(a^{2^{k-2}} - 1)$. The first term is an odd multiple of $2^k$, and it is sufficient to prove that so is the second.
Induct on $k \ge 3$ to show that $a^{2^{k-2}} - 1$ is an odd multiple of $2^k$. Since $a \equiv 3 \pmod{8}$, this is clearly the case if $k=3$, and the induction step follows from the identity $a^{2^{k-1}} - 1 = (a^{2^{k-2}} - 1)(a^{2^{k-2}} + 1) = (a^{2^{k-2}} - 1)((a^{2^{k-2}} - 1) + 2)$. This completes the proof.