By Stirling's formula, I would like to show that as $k \to \infty$, $$ \binom{-n+s}{k} \sim \text{Constant} \times k^{n-s-1}$$ with $s \in [0, n-1]$.
My work thus far has been as follows: Since $-n+s < 0$, $$ \binom{-n+s}{k} = (-1)^{k} \binom{n-s+k-1}{k} = (-1)^{k} \frac{(n-s-1+k)!}{k!(n-s-1)!}.$$
I am interested in completing this derivation.
At this point, you're nearly done, and don't even need to apply Stirling's formula. We have $$\frac{(n-s-1+k)!}{k!\,(n-s-1)!} = \frac{(k+1)(k+2)\dotsb(k+(n-s-1))}{(n-s-1)!}$$ which we can bound between $\frac{k^{n-s-1}}{(n-s-1)!}$ and $\frac{(k+(n-s-1))^{n-s-1}}{(n-s-1)!}$.
But these are off by a factor of $$\left(\frac{k + (n-s-1)}{k}\right)^{n-s-1} = \left(1 + \frac{n-s-1}{k}\right)^{n-s-1} \le \exp\left(\frac{(n-s-1)^2}{k}\right),$$ which approaches $1$ as $k \to \infty$. So we have $$\binom{-n+s}{k} \sim (-1)^k \frac{k^{n-s-1}}{(n-s-1)!}.$$