There are a couple of things going on here.
- You should have $\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^r$ as the final answer. This is because you should have had $\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}e^{kx}$ when you expanded $(e^x-1)^n$.
- The question as you posed it is not asking about the Stirling numbers of the second kind. As Michael Hardy points out in a comment, the Stirling numbers of the second kind count the number of ways to distribute $r$ distinct objects into $n$ indistinguishable boxes. (Often this is phrased as "sets" rather than "indistinguishable boxes," as the former seems clearer.) Your question involves distinct boxes.
Let's expand on the second issue, as the two problems are clearly related. Since there's some notational confusion going on, let's let $T(r,n)$ denote the number of ways to distribute $r$ distinct objects into $n$ distinct boxes with no empty box (i.e., your problem), and we'll let $S(r,n)$ denote the number of ways to distribute $r$ distinct objects into $n$ indistinguishable boxes with no empty box. Then we have the relationship $T(r,n) = n! S(r,n)$. This is because the indistinguishable boxes can be made distinguishable by applying $n$ different labels to them, and there are $n!$ ways to assign $n$ labels to $n$ boxes.
This fits with your computations above. Your (corrected) computations have $$T(r,n) = \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^r.$$
The formula you cite for the Stirling numbers of the second kind has $$S(r,n) = \frac{1}{n!}\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^r.$$
Since $\binom{n}{n-k} = \binom{n}{k}$, though, by reindexing the sum we get $$S(r,n) = \frac{1}{n!}\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^r,$$
in agreement with the argument above that $T(r,n) = n!S(r,n)$.
The most conceptual explanation uses composition of species.
Recall that your Stirling number of the first kind counts collections of $k$ cycles that together contain $n$ points.
Now, you first determine the exponential generating function for cycles:
There are $(n-1)!$ cycles of length $n$, for example, because you regard the list of elements coming after 1 in the cycle.
So, you get $Cycles(z)=\sum_n \frac{(n-1)!}{n!}z^n= \sum \frac{z^n}{n}= \log(\frac 1 {1-z})$.
Then, you determine the exponential generating function for sets of size $k$.
There is only one possibility to do so and it has size $k$:
$Sets_k(z)=\frac{z^k}{k!}$
And, now the miracle occurs:
You want to count $k$-sets of cycles and you find the exponential generating function by calculating $Sets_k$ of $Cycles$ with composition of functions.
So, you get $Sets_k(Cycles(z))= \frac{(\log(\frac 1 {1-z}))^k}{k!}$.
You can read more on this on the corresponding Wikipedia page
or you can read much more on this in the book Combinatorial Species and Tree-Like Structures by F. Bergeron, Gilbert Labelle, Pierre LeRoux.
Best Answer
Let's go from the RHS: one has \begin{align*} e^{-y}\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} & = \left(\sum_{r=0}^{+\infty} \dfrac{(-y)^r}{r!}\right) \times \left(\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} \right) \\ & = \sum_{r=0}^{+\infty} \left( \sum_{k=0}^r \dfrac{(-y)^{r-k}}{(r-k)!} \times\dfrac{k^n y^k}{k!}\right) \\ & = \sum_{r=0}^{+\infty} \dfrac{1}{r!}\left( \sum_{k=0}^r (-1)^{r-k}{r \choose k}k^n\right) y^r \\ \end{align*}
But by definition (or by the well-known explicit formula), one has $$\dfrac{1}{r!}\left( \sum_{k=0}^r (-1)^{r-k}{r \choose k}k^n\right) = \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\}$$
so you get $$e^{-y}\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} = \sum_{r=0}^{+\infty} \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\} y^r $$
Since $ \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\} = 0 $ as soon as $r \geq n$, this reduces finally to the given formula $$\boxed{e^{-y}\sum_{r= 1}^{+\infty}\dfrac{r^{n}}{r!}y^{r} = \sum_{r=0}^{n} \Big\{ \begin{matrix} n \\ r \end{matrix} \Big\} y^r }$$