I claim the largest possible $N$ is $K-1$. Obviously $N\le K-1$, thus it is enough to prove that $K-1$ works. Assume that Alice wrote $A$. Then Bob can transform $A$ to $A, A+10^n, A+2\cdot 10^n,...,A+9\cdot 10^n$. There are at least three number which are divisible by $3$ and at least two of them are not divisible by $9$. These two numbers cannot be a power of an integer. Bob chooses one of them to guarantee.