Groups with polynomial growth rate
Solution 1:
You can find some information in this preprint by Breuillard and Le Donne. They say that this is an open problem in general, and for a nilpotent group of size $n$ they say that the growth is at most $O(n^{k-2/3r})$ where $r$ is the nilpotency length. They also say that the $O(n^{k-1})$ bound holds when $r=2$ by a result of Stoll (On the asymptotics of the growth of 2-step nilpotent groups. J. London Math. Soc. (2), 58(1):38–48, 1998). I don't know if the virtually nilpotent case boils down to the nilpotent case.