Here is a start on an answer. I do not expect a nice closed-form answer.

The number of idempotent maps in the monoid of $n^n$ maps when $n > 0$ is easily seen
to be $\sum_{k=0}^{n} \binom{n}{k} k^{n-k}$, which asymptotically is
a small fraction of all the maps, but every such map is an $k$th power
for all $k > 0$.

Since for every map in $n^n$ there is a $k$th power of that map which is
idempotent, one has that the sequence $\{a_k\}$ where
$a_k$ is the number of $k$th powers of the monoid is eventually periodic,
with $a_k$ ranging from the number of idempotents to a number at most $n^n$.
The formula for $a_k$ will likely depend on the divisors of $k$, after you take
the idempotents into consideration.
If you wanted to do a literature search, I suggest Frobenius as a
starting point. Perhaps others will suggest better search terms.

There may be enumeration problems (perhaps in Richard Stanley's book(s)
Enumerative Combinatorics) which will answer the questions specifically for you. To try it yourself, consider answering the more specific
question for arbitrary $n$ but $k$ limited to, say, 5. Also, finding the period mentioned above should be routine.

Gerhard "Ask Me About System Design" Paseman, 2011.06.10