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