Summation of series involving binomial coefficients and polynomial of degree at most n-1

Let $(\Delta f)(x) = f(x) - f(x+1)$. Then your expression is $(\Delta^np)(0)$ (so apply $\Delta$ $n$ times.) Now note that $\Delta$ on a constant function is $0$ and that it lowers the degree of a non-constant polynomial by one.

Consider the binomial expansion $(e^p -1)^n = \sum_{k=0}^n \binom{n}{k} (-1)^k e^{pk}$. Then note that \begin{align} \frac{\partial^m}{\partial p^m}(e^p-1)^n \bigg |_{p=0} & = \begin{cases} 0 & \text{if } m < n \\ n! & \text{if } m = n \end{cases}. \end{align} The important thing from this relation is that if $m \ge n$ the above expression is nonzero. Then we see $\sum_{k=0}^n \binom{n}{k} (-1)^k k^m = 0$ for $m < n$.

From here it is clear that a linear combination $p(k) = \sum_{m=0}^{n-1} a_m k^m$ will work.