Fix a positive integer $k$. Let $$ f(n):= \frac{k!\binom{n}{k}}{n^k} $$ Then $\lim_{n\to \infty} f(n) = 1$. Hence $f(n) \ge 1-\epsilon$ for large $n$.
Define $n_0(\epsilon)$ as the least positive integer such that $n\ge n_0$ implies $f(n)\ge 1 -\epsilon$. Is there an asymptotic for $n_0(\epsilon)$ as $\epsilon\to 0$? A lower bound for $n_0(\epsilon)$ for fixed small $\epsilon$ would be useful too.
The approximation coming from the normal approximation of the binomial distribution is $$ k = \sqrt{-2n\ln(1-\epsilon)}.$$ To get more terms write $\Delta=-\ln(1-\epsilon)$, then by expanding $-\ln(1-i/n)$ as a Taylor series in $i$ and summing over $i=0\ldots k-1$, you get a series $$ \Delta = 1/2\,{\frac {k\, ( k-1 ) }{n}}+1/12\,{\frac {k\, ( 2\, k-1) ( k-1 ) }{n^2}}+1/12\,{\frac {{k}^{2} ( k-1) ^{2}}{{n}^{3}}} + \cdots $$ which converges if $k=O(n^c)$ for $c<1$ (but is useless if $c$ is too close to 1). The dominant term for moderately small $k$ is $k^2/2n$. You can use a series reversion method to get more terms of the inverse. I think (without much checking) that $$ k = \sqrt{2n\Delta} + \frac{3-2\Delta}{6} + \text{smaller terms},$$ and note that we are already running into the issue of $k$ being an integer.
Too long to fit in a comment and render all the math correctly... but why can't we just expand out $f_k(n)$ to $$ f_k(n) = \frac{n!}{n^k(n-k)!} = \prod_{j=1}^{k}\left(1-\frac{j-1}{n}\right) $$ Since the terms in this product expansion are indexed in decreasing order, for any $k$ we immediately have, for instance: $$ \left(1-\frac{k-1}{n}\right)^{k-1} \leq f_k(n) \leq \left(1-\frac{1}{n}\right)^{k-1}.$$ On the other hand, if we want to be more refined (as indicated by your comment), one can keep track of the product more carefully. Isolating the $n^{-1}$ terms gives us: $$f_k(n) = 1 - \left(\frac{1}{n}+\cdots + \frac{k-1}{n}\right) +\text{O}(n^{-2})$$ and of course the expression in parentheses is just $\frac{k(k-1)}{2n}$.
Following Vidit's idea, allow for $t=\frac{1}{n}$ to be real and positive. Then
$$ f_k(n)=f_k(t)=\prod_{j=1}^k\Bigl(\, 1-(j-1)t\,\Bigr). $$
Then $\newcommand{\eps}{\varepsilon}$
$$\eps=\eps(t)= 1-f(t) $$
satisfies $\eps(0)=0$ and
$$ \frac{d\eps}{dt}|_{t=0} =\sum_{j=1}^n (j-1)=\frac{k(k-1)}{2} \neq 0. $$
Thus $t\mapsto \eps(t)$ is strictly increasing for $t$ small and thus $t\mapsto \eps(t)$ is locally invertible near $t=0$. You are asking for its inverse
$$ t=t(\eps) $$
or more precisely its Taylor expansion near $\eps=0$. This can be found by implicit differentiation from the equation
$$\eps =1-f((t) \Rightarrow 1 =-\frac{df}{ft}(0)\cdot \frac{dt}{d\eps}. $$
Hence
$$\frac{1}{n_0(\eps)}=t=\frac{2\eps}{k(k-1)}+O(\eps^2). $$
Hence
$$n_0(\eps)=\eps^{-1}\frac{k(k-1)}{2}\bigl( 1+O(\eps)\bigr). $$
