The difference between $2^n$ and $n^2$ is that $2^n$ is not a function $\mod\; 10$ -- that is, $2^{n+10}$ is not congruent to $\;2^n\mod\;10$. Further $2^n$ is only eventually periodic $\mod 10^k$, $k \geq 2$. For instance $2^1$ is not congruent to any other $2^n \mod 100$. On the other hand, polynomial functions are all functions $\mod m$ : f[n+m] is congruent to f[n]$\mod m$. In short, exponential functions do not behave in the nice way polynomial functions do.
Instead of solving it as a modular equation, convert it to an explicit diophantine equation :
Solve[ 2^n - n - q 10^k == 0 && 1 <= k <= 3 && 0 <= n < If[ k == 1, 2, 1] 10^k,
{k, n, q}, Integers]
{{k -> 1, n -> 14, q -> 1637}, {k -> 1, n -> 16, q -> 6552},
{k -> 2, n -> 36, q -> 687194767}, {k -> 3, n -> 736,
q -> 3614737867146518396094859318021923665089733007170019231594754471\
5042481028623340798795186188738943961227492678378035156199978199883243\
4041296198795326329101623141899709787663433296905279066051548640942013\
290819886814068}}
The size of the quotient q for k=3 suggests that a practical limit is being reached. (I've had k=4 running for over ten minutes, and it's time for me to move on.)
