We are given that
$$r^k (r+n)! = \sum_{m=0}^k \lambda_m (r+n+m)!$$
and seek to determine the $\lambda_m$ independent of $r.$ We claim and
prove that
$$\lambda_m = (-1)^{k+m}
\sum_{p=0}^{k-m} {k\choose p} {k+1-p\brace m+1} n^p.$$
With this in mind we re-write the initial condition as
$$r^k = \sum_{m=0}^k \lambda_m m! {r+n+m\choose m}.$$
We evaluate the RHS starting with $\lambda_m$ using the EGF of the
Stirling numbers of the second kind which in the present case says
that
$${k+1-p\brace m+1} =
\frac{(k+1-p)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2-p}}
\frac{(\exp(z)-1)^{m+1}}{(m+1)!} \; dz.$$
We obtain for $\lambda_m$
$$(-1)^{k+m}
\sum_{p=0}^{k-m} n^p {k\choose p}
\frac{(k+1-p)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2-p}}
\frac{(\exp(z)-1)^{m+1}}{(m+1)!}
\; dz.$$
The inner term vanishes when $p\ge k+2$ but in fact even better it
also vanishes when $p\gt k-m$ which implies $m+1\gt k+1-p$ because
$(\exp(z)-1)^{m+1}$ starts at $[z^{m+1}]$ and we are extracting the
term on $[z^{k+1-p}].$
Hence we may extend $p$ to infinity without picking up any extra
contributions to get
$$(-1)^{k+m}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
\frac{(\exp(z)-1)^{m+1}}{(m+1)!}
\sum_{p\ge 0} (k+1-p) \frac{n^p z^p}{p!}
\; dz.$$
This is
$$(-1)^{k+m}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
\frac{(\exp(z)-1)^{m+1}}{(m+1)!}
((k+1)-nz) \exp(nz) \; dz.$$
Substitute this into the outer sum to get
$$(-1)^{k}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
((k+1)-nz) \exp(nz)
\\ \times \sum_{m=0}^k {r+n+m\choose m} (-1)^m
\frac{(\exp(z)-1)^{m+1}}{m+1}
\; dz.$$
We have
$${r+n+m\choose m} \frac{1}{m+1}
= {r+n+m\choose m+1} \frac{1}{r+n}$$
and hence obtain
$$\frac{(-1)^{k}}{r+n}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
((k+1)-nz) \exp(nz)
\\ \times \sum_{m=0}^k {r+n+m\choose m+1} (-1)^m
(\exp(z)-1)^{m+1}
\; dz.$$
We may extend $m$ to $m\gt k$ in the remaining sum because the term
$(\exp(z)-1)^{m+1}$ as before starts at $[z^{m+1}]$ which would then
be $\gt k+1$ but we are extracting the coefficient on $[z^{k+1}],$
which makes for a zero contribution.
Continuing we find
$$-\sum_{m\ge 0} {r+n+m\choose r+n-1} (-1)^{m+1}
(\exp(z)-1)^{m+1}
\\ = 1 - \frac{1}{(1-(1-\exp(z)))^{r+n}}
= 1 - \exp(-(r+n)z).$$
We get two pieces on substituting this back into the main integral,
the first is
$$\frac{(-1)^{k}}{r+n}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
((k+1)-nz) \exp(nz) \; dz
\\ = \frac{(-1)^{k}}{r+n} (k+1)! \frac{n^{k+1}}{(k+1)!}
- \frac{(-1)^k}{r+n} k! n \frac{n^{k}}{k!} = 0.$$
and the second is
$$\frac{(-1)^{k+1}}{r+n}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
((k+1)-nz) \exp(nz) \exp(-(r+n)z) \; dz
\\ = \frac{(-1)^{k+1}}{r+n}
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+2}}
((k+1)-nz) \exp(-rz) \; dz
\\ = \frac{(-1)^{k+1}}{r+n} (k+1)! \frac{(-r)^{k+1}}{(k+1)!}
- \frac{(-1)^{k+1}}{r+n} k! n \frac{(-r)^k}{k!}
\\ = \frac{1}{r+n} (k+1)! \frac{r^{k+1}}{(k+1)!}
+ \frac{1}{r+n} k! n \frac{r^k}{k!}
\\ = \frac{1}{r+n} r^{k+1} + \frac{1}{r+n} n r^k
= r^k.$$
This concludes the argument.
Addendum Nov 27 2016. Markus Scheuer proposes the identity
$$\lambda_m = (-1)^{m+k} \sum_{p=m}^k {p\brace m}
{k\choose p} (n+1)^{k-p}.$$
To see that this is the same as what I presented we extract the
coefficient on $[n^q]$ to get
$$(-1)^{m+k} \sum_{p=m}^k {p\brace m}
{k\choose p} {k-p\choose q}.$$
Now we have
$${k\choose p} {k-p\choose q} =
\frac{k!}{p! q! (k-p-q)!}
= {k\choose q} {k-q\choose p}.$$
We get
$$(-1)^{m+k} {k\choose q}
\sum_{p=m}^k {p\brace m} {k-q\choose p}.$$
We now introduce with deployment of the Egorychev method in mind
$${k-q\choose p} = {k-q\choose k-q-p} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k-q-p+1}} (1+z)^{k-q}
\; dz.$$
This certainly vanishes when $p\gt k-q$ so we may extend $p$ to
infinity, getting for the sum
$$(-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k-q+1}} (1+z)^{k-q}
\sum_{p\ge m} {p\brace m} z^p
\; dz.$$
Using the OGF of the Stirling numbers of the second kind this becomes
$$(-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{k-q+1}} (1+z)^{k-q}
\prod_{l=1}^m \frac{z}{1-lz}
\; dz.$$
Now put $z/(1+z) = w$ to get $z = w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$
to obtain
$$(-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k-q}} \frac{1-w}{w} \frac{1}{(1-w)^2}
\prod_{l=1}^m \frac{w/(1-w)}{1-lw/(1-w)}
\; dw
\\ = (-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k-q+1}} \frac{1}{1-w}
\prod_{l=1}^m \frac{w}{1-w-lw}
\; dw
\\ = (-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k-q+1}} \frac{1}{1-w}
\prod_{l=1}^m \frac{w}{1-(l+1)w}
\; dw
\\ = (-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k-q+2}} \frac{w}{1-w}
\prod_{l=2}^{m+1} \frac{w}{1-lw}
\; dw
\\ = (-1)^{m+k} {k\choose q}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{k-q+2}}
\prod_{l=1}^{m+1} \frac{w}{1-lw}
\; dw
\\= (-1)^{m+k} {k\choose q} {k-q+1\brace m+1}.$$
This is the claim and we are done.
Best Answer
I like Knuth's notation for falling factorials better:
$$ \alpha^{\underline{h}} = \alpha \cdot (\alpha - 1) \cdot \dotsm \cdot (\alpha - h + 1) $$
First note that:
$$ \Delta \alpha^{\underline{h}} = (\alpha + 1)^{\underline{h}} -\alpha^{\underline{h}} = (\alpha + 1) \cdot \alpha^{\underline{h - 1}} - \alpha^{\underline{h - 1}} \cdot (\alpha - h + 1) = h \alpha^{\underline{h - 1}} $$
This suggests:
$$ \sum_{0 \le k \le n} (\alpha + k)^{\underline{h}} = \frac{(\alpha + n + 1)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} $$
This we prove by induction.
Base: $n = 0$ gives:
$\begin{align} \sum_{0 \le k \le 0} (\alpha + k)^{\underline{h}} &= \alpha^{\underline{h}} \\ \frac{(\alpha + 1)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} &= \frac{1}{h + 1} \Delta \alpha^{\underline{h + 1}} \\ &= \alpha^{\underline{h}} \end{align}$
This checks out.
Induction: Assume it is true for $n$, look at $n + 1$:
$\begin{align} \sum_{0 \le k \le n + 1} (\alpha + k)^{\underline{h}} &= \sum_{0 \le k \le n} (\alpha + k)^{\underline{h}} + (\alpha + n + 1)^{\underline{h}} \\ &= \frac{(\alpha + n + 1)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} + (\alpha + n + 1)^{\underline{h}} \\ &= \frac{(\alpha + n + 1)^{\underline{h}} \cdot (\alpha + n + 1 - h)} {h + 1} + \frac{(\alpha + n + 1)^{\underline{h}} \cdot (h + 1)} {h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} \\ &= \frac{(\alpha + n + 1)^{\underline{h}} \cdot (\alpha + n + 2)} {h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} \\ &= \frac{(\alpha + n + 2)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} \end{align}$
This is exactly as claimed.
For your second sum, note that:
$$ (\alpha + k)^{\underline{h}} x^{\alpha + k - h} = \frac{\mathrm{d}^h}{\mathrm{d} x^h} x^{\alpha + k} $$
Thus the sum is essentially:
$\begin{align} \sum\limits_{k=0}^n (\alpha + k)^{\underline{h}} r^k &= r^{h - \alpha} \sum\limits_{k=0}^n (\alpha + k)^{\underline{h}} r^{\alpha + k - h} \\ &= r^{h - \alpha} \left. \frac{\mathrm{d}^h}{\mathrm{d} x^h} \sum\limits_{k=0}^n x^{\alpha + k} \right|_{x = r} \\ &= r^{h - \alpha} \left. \frac{\mathrm{d}^h}{\mathrm{d} x^h} \left(x^\alpha \sum\limits_{k=0}^n x^k\right) \right|_{x = r} \\ &=\left.r^{h-\alpha} \frac{d^h}{d x^h} \left( \frac{x^\alpha - x^{\alpha+n+1}}{1- x} \right)\right|_{x=r} \\ &=r^{h-\alpha} \sum\limits_{l=0}^h \binom{h}{l} \left(\alpha^{\underline{h-l}} r^{\alpha-(h-l)} - (\alpha+n+1)^{\underline{h-l}} r^{\alpha+n+1-(h-l)}\right) \cdot \frac{l!}{(1-r)^{l+1}} \\ &= \frac{1}{(1-r)^{h+1}} \sum\limits_{l=0}^h \binom{h}{l} \left(\alpha^{\underline{h-l}} r^{l} - (\alpha+n+1)^{\underline{h-l}} r^{n+1+l}\right) \cdot l! (1-r)^{h-l} \\ &= \frac{h!}{(1-r)^{h+1}} \sum\limits_{l=0}^h \frac{1}{(h-l)!} \left(\alpha^{\underline{h-l}} r^{l} - (\alpha+n+1)^{\underline{h-l}} r^{n+1+l}\right) \cdot (1-r)^{h-l} \\ &= \frac{h!}{(1-r)^{h+1}} \sum\limits_{l=0}^h \left(\binom{\alpha}{h-l} r^{l} - \binom{\alpha+n+1}{h-l} r^{n+1+l}\right) \cdot (1-r)^{h-l} \\ &= \frac{h!}{(1-r)} \left\{ \binom{\alpha}{h} \cdot F_{2,1} \left[\begin{array}{ll}1 & -h \\ \alpha-h+1 \end{array};\frac{r}{r-1}\right] - r^{n+1} \binom{\alpha+n+1}{h} \cdot F_{2,1} \left[\begin{array}{ll}1 & -h \\ \alpha+n-h+2 \end{array};\frac{r}{r-1}\right] \right\} \end{align}$
This is quite ugly. The remaining sum is geometric, and can be expressed as a fraction. Leibnitz' formula for multiple derivatives of a product reduce that somewhat, but it is still a mess. If $h$ is small integer, perhaps a CAS gives somewhat manageable.
Note: It is a matter of taste whether an expression is ugly or not. In my opinion the final result has a closed form if we use hypergeometric functions.