Let $p(z)=\prod_{i=1}^n (z-\lambda_i)$ be characteristic polynomial of $A$. Denote by $r_k(z)=c_0(k)+c_1(k)z+\dots +c_{n-1}(k)z^{n-1}$ the remainder of polynomial $z^k$ modulo $p(z)$. Then $A^k=\sum_{i=0}^{n-1} c_i(k) A^i$, $\|A^k\|\leqslant 10^n \sum |c_i(k)|$. Well, $c_i(k)$ may be found from the linear system $\sum c_i(k) \lambda_j^i=\lambda_j^{k}$ (we may now suppose that all $\lambda$'s are different and then use continuity of the solution). Solve this system using Kramer's rule, we get that $c_i(k)$ are ratios of some antisymmetric determinant (namely, Vandermonde determinant without $i$-th column $\lambda_j^i$ but with $\lambda_j^k$ instead) and Vandermonde determinant itself. This is known as Schur's function and we really need that it has non-negative coefficients as a polynomial in $\lambda$'s. 

Thus maximal value of $|c_i(k)|$ for $|\lambda_i|\leqslant \rho$ is obtained if $\lambda_1=\lambda_2=\dots=\lambda_n=\rho$. Let me now assume that $\rho=1$, after that I have to multiply it by $\rho^{k-i}$. We have to find remainder of $z^k$ modulo $(z-1)^n$. Not a big deal: 
$$z^k=((z-1)+1)^k\equiv 1+k(z-1)+\binom{k}2 (z-1)^2+\dots+\binom{k}{n-1}(z-1)^{n-1}\pmod {(z-1)^n}.$$ 
Sum of abosulte values of coefficients of this polynomial admits a bound like $2^nk^n$. Totally we get $$\|A^k\|\leqslant (20 k)^n \rho^{k-n},$$
this is small for $k=n^c$ for any fixed $c>1$.