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.)