Polynomially sized Folner sets Let $\Gamma$ be a finitely-generated group with a fixed finite generating set $S$.
Then, $\Gamma$ is amenable if and only if it there is a sequence $(F_n)_{n=1}^{\infty}$ of finite subsets of $\Gamma$, whose union is $\Gamma$, such that the boundary of $F_n$ with respect to $S$ is of size at most $\frac{1}{n}\cdot|F_n|$ (this is a "Folner sequence").
Let's say that $\Gamma$ is "polynomially amenable" if the sets $F_n$ above can be chosen such that $|F_n|$ is bounded by a polynomial in $n$.
Then, groups of polynomial growth are polynomially amenable.

Are there polynomially amenable groups which are not of polynomial growth? If so, I'd like to know many examples.


No: the Følner function grows at least as fast as the word growth: this is due to Varopoulos. Hence a group with polynomially bounded Følner function has polynomially bounded growth (this is purely analytic, not related to Gromov's theorem).
See Drutu's slides:
http://people.maths.ox.ac.uk/drutu/tcc2/TCC5-slides.pdf
PS your assumption that $(F_n)$ covers the group is quite not natural and inconvenient to handle, and usually not part of the definition of Følner sequences. (Although it is easy to find a covering sequence for every countable amenable group.)
