This should be a decently simple exercise in analysis, but the bounds I'm finding are not particularly tight. I was wondering if there is some clever way to approximate the following:
\begin{align*} \sum_{i=0}^{m-k}\binom{m-k}{i}\sum_{j=0}^{m-i}(-1)^j\binom{m-i}{j}(m-i-j)^n \end{align*}
In terms of $m,k$ and $n$
You might find it easier to derive bounds if you first simplify this combinatorially.
The inner sum counts the strings of length $n$ from an alphabet of $m-i$ letters that use all letters. Thus the outer sum counts the strings of length $n$ from an alphabet of $m$ letters that include all of $k$ particular letters by summing over all subsets of the remaining $m-k$ letters that might not appear. You can count the same thing more directly by inclusion–exclusion by choosing $j$ out of the $k$ letters to omit, which shows that your sum is equal to
$$ \sum_{j=0}^k(-1)^j\binom kj(m-j)^n\;. $$
(This is $(-1)^{n+k}$ times the $k$-th forward difference of $x^n$ evaluated at $x=-m$; see Wikipedia.)