For sums like this, usually one term dominates. Taking $p(n)=n^d$ to play with, consider when $\binom{(n-k)^d}{k} \lt \binom{(n-k-1)^d}{k+1}$ stops holding. This is not far from when $(k+1) \lt (\frac{n-k-1}{n-k})^{kd} ((n-k-1)^d - k)$ stops holding, which in turn happens not far from when $(\frac{n-k}{n-k-1})^k \gt (n-k-1)$ which in turn doesn't happen until somewhere near $k \gt (n-k-1)\log{n-k-1}$. As recommended in the comments, you should use calculus and similar approximations to find the actual value of $k$, but it will usually be $k \gt n/2$. Once you have that term, the sum will usually be not much larger than the term.

Gerhard "There's An Order To This" Paseman, 2014.06.13

For sums like this, usually one term dominates. Taking $p(n)=n^d$ to play with, consider when $\binom{(n-k)^d}{k} \lt \binom{(n-k-1)^d}{k+1}$ stops holding. This is not far from when $(k+1) \lt (\frac{n-k-1}{n-k})^{kd} ((n-k-1)^d - k)$ stops holding, which in turn happens not far from when $(\frac{n-k}{n-k-1})^k \gt (n-k-1)$ which in turn doesn't happen until somewhere near $k \gt (n-k-1)\log(n-k-1)$. (For large $n, k \approx n(\log(n)-1)/\log n$ is a good value to start with in an approximation routine.) As recommended in the comments, you should use calculus and similar approximations to find the actual value of $k$, but it will usually be $k \gt n/2$. Once you have that term, the sum will usually be not much larger than the term.

Gerhard "There's An Order To This" Paseman, 2014.06.13