Seems like the "greedy algorithm" works...
Suppose $A_0$ is finitely generated as a $k$-algebra, say by $a_1, \ldots, a_m$ and $A_{>0}$ is finitely generated as an $A$-module, say by $b_1, \ldots, b_n$. I claim that $\{a_1, \ldots, a_m, b_1, \ldots, b_n\}$ generate $A$ as a $k$-algebra.
Indeed, given any $x \in A$, if $x \in A_0$ then this is obvious. Otherwise, $x \in A_{>0}$ so we can write
$$ x = b_1 x_1' + b_2 x_2' + \ldots $$
with the $x_i' \in A$ having strictly lower degrees. Then we are done by induction.
Now for the other direction. If $A$ is finitely generated as a $k$-algebra, write a finite list of generators $\{a_1, \ldots, a_m, b_1, \ldots, b_n\}$ with $\deg a_i = 0$ and $\deg b_i >0$. Then $A_0$ is generated as a $k$-algebra by $\{a_1, \ldots, a_m\}$, since by definition everything in $A$ is a polynomial expression in these generators, but by degree considerations no such expression involving a $b$ can be in $A_0$.
Next I claim that $\{b_1, \ldots, b_n\}$ generates $A_{>0}$ as an $A$-module. Indeed, any $x \in A_{>0}$ is a polynomial expression in the generators, and again by degree considerations every monomial must involve at least one of the $b_i$.