For integers $n \ge 0$ and $k \ge 2$, define $E^k_n$ as the set of tuples $b \in \{0,\ldots, k\}^{\log n}$, such that $n = \sum_{0 \le i \le \log n} b_i 2 ^i.$
Note that the only element of $E^1_n$ is simply $n$ in base $2$.
Clearly $|E^k_n| \le k^{\log n} = n^{\log k}$, but what is a better, ideally tight, upperbound?
My guess is that $n^{\frac{\log k}{\log \log n} }$ is an upperbound.
Here is an answer for certain values of $k$, which disproves your guess and suggests an alternate conjecture.
Suppose that $k=2^\ell-1$ for some $\ell\ge2$. Then each digit $b_i$ can be written uniquely in binary: $b_i = \sum_{j=0}^{\ell-1} a_{i,j}2^j$ with each $a_{i,j}\in\{0,1\}$. Thus $$ \sum_{0\le i\le \log n} b_i 2^i = \sum_{0\le i\le \log n} \sum_{j=0}^{\ell-1} a_{i,j}2^j 2^i = \sum_{j=0}^{\ell-1} 2^j \sum_{0\le i\le \log n} a_{i,j} 2^i. $$ But note that for fixed $j$, the inner sum simply equals every integer between $0$ and $2^{\log n+1}-1$ once each. In particular, the number of solutions to $$ n = \sum_{0\le i\le \log n} b_i 2^i $$ is the same as the number of solutions to $$ n = \sum_{j=0}^{\ell-1} 2^j m_j $$ with each $0\le m_j < 2^{\log n+1}$. The number of such solutions is easy to work out asymptotically; if I made no mistakes, the answer is approximately \begin{align*} \frac{n^{\ell-1}}{(\ell-1)!2^{\ell(\ell-1)/2}} &= \frac{n^{\log_2(k+1)-1}}{(\log_2(k+1)-1)!2^{\log_2(k+1)(\log_2(k+1)-1)/2}}. \end{align*} Since the denominator doesn't depend on $n$, this shows that for these values of $k$, the function grows faster than $n^{(\log k)/\log\log n}$.
My suspicion is that the correct rate of growth is something like $n^{\log_2 k - 1}$ for all $k$. (The $n^{-1}$ factor makes sense since there are $kn$ possible values for the sum and we want to single out one of them.)
