I have obtained a formula for the generating function of your sequence.
Let $S_n$ be defined as in the quesion. We extend the definition to $n = 0$ by demanding $0^0 = 0$, hence $S_0 = 0$.
Consider $S(t) = \sum_{n\geq 0} S_n t^n$. I will work out a formula for $S(t)$.
\begin{eqnarray*} S(t) &=& \sum_{n=0}^\infty \sum_{j = 0}^n\frac{(-e)^{-j}}{j!}(n - j)^j t^n\\ &=& \sum_{j = 0}^\infty \frac{(-e)^{-j}}{j!}t^j\sum_{n = 0}^\infty n^jt^n\\ &=& \sum_{j = 0}^\infty \frac{(-e^{-1}t)^j}{j!}\frac{tA_j(t)}{(1 - t)^{j + 1}}\\ &=& \frac{t}{1 - t}\sum_{j = 0}^\infty A_j(t)\frac{(\frac{e^{-1}t}{t - 1})^j}{j!}\\ &=& \frac{t}{1 - t}\frac{t - 1}{t - e^{e^{-1}t}}\\ &=& \frac{t}{e^{e^{-1}t} - t}. \end{eqnarray*}
Explanation for the calculation:
The key step is $\sum_{n\geq 0} n^jt^n = \frac{tA_j(t)}{(1 - t)^{j + 1}}$, where $A_j(t)$ is the Eulerian polynomial. We then use the generating function $\sum_{j \geq 0}A_j(t)\frac{x^j}{j!} = \frac{t - 1}{t - e^{(t - 1)x}}$.
It is then reasonable to make the change of variable $T = e^{-1}t$, which leads to $S_n = e^{-n}S'_n$, where the sequence $(S'_n)_n$ has generating function $\frac{eT}{e^T - eT}$. This at least gives a numerically better way to calculate the numbers $S_n$.
And the question becomes to prove that $S'_n = 2n + \frac{2}{3} + o(1)$, where $S'_n$ is the $n$-th coefficient of the Taylor expansion of the function $\frac{T}{e^{T - 1} - T}$ at $T = 0$.
I'm however not able to proceed further...
One may try to subtract $\sum_{n \geq 0}(2n + \frac{2}{3})T^n$, which is a rational fraction, and try to show that the difference has Taylor coefficients tending to $0$. But this doesn't seem to help much.
Also the $n$-th Taylor coefficient could be calculated via a residue at $0$, but again doesn't seem to help much.
Experimentally, it seems that the parameter $e^{-1}$ is quite important. For this parameter, we indeed have $S_n = (2n + \frac{2}{3} + o(1))e^{-n}$, as Henri Cohen stated in the comment.
For other parameters, it seems that the sequence always decreases exponentially (or sub-exponentially), although something larger than $e^{-1}$ will lead to negative terms.