you can rewrite your last sum as
$$
\eqalign{
& S(n,m,k) = \sum\limits_{i = 0}^{k - 1} {\left( { - 1} \right)^{\,i}
\left( \matrix{ n - k \cr m - k + i \cr} \right)
\left( \matrix{ k - 1 \cr i \cr} \right)}
\quad \left| \matrix{ \,n,m,k \in Z \hfill \cr \,1 \le k \hfill \cr} \right.\quad = \cr
& = \left( { - 1} \right)^{\,k - 1} \sum\limits_{i = 0}^{k - 1} {\left( { - 1} \right)^{\,k - 1 - i}
\left( \matrix{ n - k \cr m - 1 - \left( {k - 1 - i} \right) \cr} \right)
\left( \matrix{ k - 1 \cr \left( {k - 1 - i} \right) \cr} \right)} = \cr
& = \left( { - 1} \right)^{\,k - 1} \sum\limits_{j = 0}^{k - 1}
{\left( \matrix{ n - k \cr m - 1 - j \cr} \right)1^{\,m - 1 - j}
\left( \matrix{ k - 1 \cr j \cr} \right)\left( { - 1} \right)^{\,j} } = \cr
& = \left( { - 1} \right)^{\,k - 1} \left[ {x^{\,m - 1} } \right]
\left( {1 + x} \right)^{n - k} \left( {1 - x} \right)^{k - 1} = \cr
& = \left[ {x^{\,m - 1} } \right]\left( {1 + x} \right)^{n - k} \left( {x - 1} \right)^{k - 1}
\quad = \quad \cdots \cr}
$$
the result depending on whether you consider that $n,m$ might also be negative.
But unfortunately the analysis fragments down into many different cases.
Even assuming as per your comment that all the parameters are positive, you come
to distinguishing whether $n-k$ is positive or not.
Suppose it is positive
$$
\left\{ \matrix{
1 \le k \le n \hfill \cr
1 \le n \hfill \cr} \right.
$$
then
$$
\eqalign{
& S(n,m,k) =
\left[ {x^{\,m - 1} } \right]\left( {1 + x} \right)^{n - k} \left( {x - 1} \right)^{k - 1} = \cr
& = \left[ {x^{\,m - 1} } \right]\left( {x + 1} \right)^a \left( {x - 1} \right)^b \cr}
$$
and here you shall distinguish whether
$$
b \le a\;\left( {2k \le n + 1} \right)
$$
in which case you can write
$$
\eqalign{
& S(n,m,k) = \left[ {x^{\,m - 1} } \right]\left( {x + 1} \right)^{a - b} \left( {x^{\,2} - 1} \right)^b = \cr
& = \left[ {x^{\,m - 1} } \right]\sum\limits_j {\left( { - 1} \right)^{\,s - j}
\left( \matrix{a - b \cr j \cr} \right)\left( \matrix{ b \cr s - j \cr} \right)x^{\,2s - j} } = \cr
& = \sum\limits_j {\left( { - 1} \right)^{\,{{m - 1 - j} \over 2}}
\left( \matrix{ a - b \cr j \cr} \right)\left( \matrix{b \cr {{m - 1 - j} \over 2} \cr} \right)} \cr}
$$
and in case, split between even \ odd $m$ ....