The key idea in your proof works for other bases as well, and other numbers of digits. 

**Lemma:** There is a bound based on $k$ and $b$ for the greatest power of $b$ which could be necessary in a representation of a real number with magnitude under $1$ as a polynomial in $b$, the magnitudes of whose coefficients add up to at most $k$.
 
**Proof:** For any sequence of such polynomials of unbounded degree, we find a polynomial of finite degree with $b$ as a root from a pointwise limit of the coefficients of the first $log_b(k-1)$ terms of the polynomials. This means the use of those higher powers of $b$ was removable.

Let this bound be $p(b,k)$. When you count the sums of powers of $b$ which could be used to represent a number up to $n$, you only need to consider powers of $b$ up to $\log_b(n+k) + p(b,k)$. So you get at most $(1+2 log_b(n+p))^k$ representable numbers out of $n$, and for large $n$, some numbers can't be represented.