I don't know of a paper proving the result, but I can prove it for you now. In fact, the methods in the paper you link generalize to an arbitrary base $g\gt2$. The authors of the paper don't seem to think that it generalizes quite so easily, as in the Open Problems section they state that "For bases $b\gt2$ there is the problem of having more than two possible digits. What kinds of bounds might be placed on counts of 1's and 2's for ternary expansions of algebraic numbers?". Hopefully I have not made any major mistakes...

[Edit: A paper by Bugeaud, *On the b-ary expansion of an algebraic number*, available from his homepage gives lower bounds on the number of nonzero digits in an irrational algebraic number. There, he references the paper linked in the question, saying "Apparently, their approach does not extend to a base $b$ with $b\ge3$". However, he has just responded to this question, agreeing that the method does indeed generalize. So I'm more confident about my proof now.]

Use $\#(x,N)$ to denote the number of nonzero base-$g$ digits in the expansion of $x$, up to and including the $N$'th digit after the 'decimal' point, then what you are asking for is implied by the following.

If $x$ is irrational and satisfies a rational polynomial of degree $D$ then $\#(x,N)\ge cN^{1/D}$ for a positive constant $c$ and all $N$.

First, I'll introduce some notation similar to that used in the linked paper. Use $r_1(n)$ to denote the $n$'th base-$g$ digit of $x$, so that $0\le r_1(n)\le g-1$ and
$$
x=\sum_nr_1(n)g^{-n}.
$$

It's enough to consider $1\le x\lt2$, so I'll do that throughout. Then $r_1(n)=0$ for $n\lt0$ and $r_1(0)=1$. Also use $r_d(n)$ to denote
$$
r_d(n)=\sum_{p_1+p_2+\cdots+p_d=n}r_1(p_1)r_1(p_2)\cdots r_1(p_d)=\sum_{j+k=n}r_1(j)r_{d-1}(k)
$$
This satisfies the inequalities $r_d(n)\ge r_1(0)r_{d-1}(n)=r_{d-1}(n)$ and
$$
\sum_{n\le N}r_d(n)\le(g-1)^d\#(x,N)^d\le(g-1)^d(N+1)^d.\qquad\qquad{\rm(1)}
$$
Also, raising $x$ to the $d$'th power gives
$$
x^d=\sum_nr_d(n)g^{-n},
$$
which differs from the base $g$ expansion of $x^d$ only because $r_d(n)$ can exceed $g$. We also introduce notation for the expansion of $x^d$ with the digits shifted to the left $R$ places and truncated to leave the fractional part,
$$
T_d(R)=\sum_{n\ge1}r_d(R+n)g^{-n},
$$
so that $g^Rx^d-T_d(R)$ is an integer. This can also be bounded, using (1),
$$
\begin{array}{rl}
\displaystyle T_d(R)&\displaystyle\le\sum_{n\ge1}(g-1)^d(R+n+1)^dg^{-n}\\ &\displaystyle\le\sum_{n\ge1}(g-1)^d(R+1)^d(n+1)^dg^{-n}\\
&\displaystyle\le C_d(R+1)^d
\end{array}
$$
where $C_d=\sum_{n\ge1}(g-1)^d(n+1)^dg^{-d}$ is a constant independent of $R$.

Now suppose that $x$ satisfies an integer polynomial of degree $D\gt1$,
$$
A_Dx^D+A_{D-1}x^{D-1}+\cdots+A_1x+A_0=0
$$
with $A_D\gt0$. It follows that
$$
T(R)\equiv\sum_{d=1}^D A_dT_d(R)
$$
is an integer for each $R$.
The following is similar to Theorem 3.1 in the linked paper.

**Lemma 1**: For all sufficiently large $N$, there exists $n\in(N/(D+1),N)$ with $r_1(n)\gt0$.

*Proof:* This is a consequence of Liouville's theorem for rational approximation. If the statement was false then setting $m=\lfloor N/(D+1)\rfloor$, $p=\sum_{n=0}^mr_1(n)g^{-n}$, $q=g^{m}$ gives infinitely many approximations $\vert x-p/q\vert=q^{-D}o(1)$ as $N$ increases, contradicting Liouville's theorem.

In Lemma 1, Roth's theorem could have been used to reduce the $D+1$ term to $2+\epsilon$. In fact, Ridout's theorem as discussed in the comments can be used to reduce it even further to $1+\epsilon$. This isn't needed here, so I just used the more elementary Liouville's theorem.

Lemma 6.1 from the linked paper generalizes to base $b$, and puts upper bounds on the number of times at which $T(n)$ can be nonzero.

**Lemma 2**: For large enough $N$, setting $K=\lceil 2D\log_g N\rceil$ gives
$$
\sum_{1\le R\le N-K}T_d(R) < (g-1)^{d-1}\#(x,N)^d+1
$$
for $1\le d\le D$ and so,
$$
\sum_{1\le R\le N-K}\vert T(R)\vert\le\sum_{d=1}^D\vert A_d\vert ((g-1)^{d-1}\#(x,N)^D+1)
$$

*Proof:* Using similar inequalities to the proof used in the linked paper,
$$
\begin{array}{rl}
\displaystyle\sum_{1\le R\le N-K}T_d(R) &\displaystyle=\sum_{m\ge1}g^{-m}\sum_{R\le N-K}r_d(R+m)\\
&\displaystyle\le\sum_{m=1}^Kg^{-m}\sum_{R\le N}r_d(R)+g^{-K}\sum_{m > K}g^{K-m}\sum_{R\le N-K}r_d(R+m)\\
&\displaystyle \le \frac{1}{g-1}\sum_{R\le N}r_d(R)+g^{-K}\sum_{K\le R\le N}T_d(R)\\
&\displaystyle\le(g-1)^{d-1}\#(x,N)^d+g^{-K}NC_d(N+1)^d.
\end{array}
$$
The final term is bounded by $C_d(N+1)^{d+1}/N^{2D}$ which will be less than 1 for $N$ large.

Lemma 6.2 also generalizes, which gives blocks where $T(R)$ is nonzero.

**Lemma 3**: Let $R_1\lt R_2$ be positive integers with $r_{D-1}(R)=0$ for all $R\in(R_0,R_1]$ and $T(R_1)\gt0$. Then $T(R)\gt0$ for all $R\in[R_0,R_1]$.

*Proof:*
We have the following relation for $T$,
$$
T(R-1)=\frac{1}{g}T(R)+\frac{1}{g}\sum_{d=1}^D A_dr_d(R).
$$
As $r_d(n)\ge r_{d-1}(n)$, the hypothesis implies that $r_d(R)=0$ for all $1\le d\le D-1$ and $R\in(R_0,R_1]$. Therefore,
$$
T(R-1)=\frac{1}{g}T(R)+\frac{1}{g}A_Dr_D(R)\ge \frac{1}{g}T(R).
$$
Assuming inductively that $T(R)\gt0$ gives $T(R-1)\gt0$.

Putting this together gives the result (Theorem 7.2 in the linked paper).

**Theorem 4**: There is a constant $c$ such that, for all sufficiently large $N$
$$
\#(x,N)>cN^{1/D}
$$

*Proof*:
Suppose not, then for any $\delta\gt0$, there are infinitely many $N$ with $\#(x,N)\lt\delta N^{1/D}$ and, using (1),
$$
\sum_{n\le N}r_{D-1}(n)\le \delta N^{1-1/D}\qquad\qquad{\rm(2)}
$$
In particular, the proportion of integers $R$ with $r_{D-1}(R)\gt0$ goes to $0$. Let $0=R_1\lt R_2\lt\cdots\lt R_M\le N$ be those integers in the range $[0,N]$ with $r_{D-1}(R_k)\gt0$ and set $R_{M+1}=N$. Then (2) gives $M+1\le\delta N^{1-1/D}$, and $r_d(R)=0$ for $d\le D-1$ and $R$ in any of the ranges $(R_i,R_{i+1})$. So, $T_d(R-1)=g^{R-R_{i+1}}T_d(R_{i+1}-1)$.

Fixing $\epsilon\gt0$ and letting $I$ denote the numbers $i$ with $R_{i+1}-R_i\gt\epsilon N^{1/D}$ gives
$$
\sum_{i\in I}(R_{i+1}-R_i)\ge N - (M+1)\epsilon N^{1/D}\ge N(1-\epsilon \delta).
$$
So, the intervals $(R_i,R_{i+1})$ larger than $\epsilon N^{1/D}$ cover most of the interval $[0,N]$, as long as $\epsilon\delta$ is small enough.

If $R$ is in the range $(R_i,R_{i+1}-D\log_gN)$ and $r_D(R)\gt0$ then $T(R-1)\gt0$:
$$
T(R-1)\ge \frac{1}{g}A_D-g^{R-R_{i+1}}\sum_{d=1}^{D-1}\vert A_d\vert T_d(R_{i+1}-1)
\ge\frac1g-N^{-D}\sum_{d=1}^{D-1}\vert A_d\vert C_d R_{i+1}^d
$$
which is positive, so long as $N$ is chosen large enough.

Assuming that $N$ is large enough, by Lemma 1, for each $i$ in $I$, there is
$$
j\in\left(\frac{1}{D+1}(R_{i+1}-R_i-D\log_gN),R_{i+1}-R_i-D\log_gN\right)
$$
with $r_1(j)\gt0$. Then, $r_D(R_i+j)\ge r_{D-1}(R_i)r_1(j)$ is positive, so $T(R_i+j-1)\gt0$. Lemma 3 implies that $T(R_i+j)$ is positive for all $0\le j\lt(R_{i+1}-R_i-D\log_gN)/(D+1)$.
$$
\sum_{1\le n< N-2D\log_g N}\vert T(n)\vert\ge\frac{1}{D+1}\sum_{i\in I}(R_{i+1}-R_i-2D\log_gN)
\ge\frac{N(1-\epsilon\delta)}{D+1}-2\delta N^{1-1/D}\log_gN
$$
This contradicts Lemma 2, which gives, for $N$ large,
$$
\sum_{1\le n< N-2D\log_g N}\vert T(n)\vert =O(\delta^D N).
$$

Rational approximations to algebraic numbers(dx.doi.org/10.1112/S0025579300001182). Not free access, but it is quoted inAn explicit version of the theorem of Roth-Ridout(seminariomatematico.dm.unito.it/rendiconti/cartaceo/53-3.html) Theorem 2 (Ridout's theorem). This does indeed do the job! Many thanks for that. In fact you only need the denominators to have factors from some finite set of primes, which covers Z(k) growing exponentially and any base. Still, the case for Z(k) merely dominating any polynomial seems to be open. – George Lowther Oct 11 '10 at 1:25