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 >= 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 function 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 -> 361473786714651839609485931802192366508973300717001923159475447
1504248102862334079879518618873894396122749267837803515619997819988324
3404129619879532632910162314189970978766343329690527906605154864094201
3290819886814068}}
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.)