Polynomial satisfying a relation for all positive integers

It is not contradictory. Consider $P(x)=x$ of degree $1$ then $$P(1)+P(2)+\dots +P(n)=1+2+\dots +n=\frac{n(n+1)}{2}$$ which is of degree $2$. Note also that the sum has not a fixed number of terms, it increases with $n$.

As regards your specific problem, the polynomial $$P(x)-(x^5-(x-1)^5)$$ has infinite zeros, i.e. all the positive integers, so it is the zero polynomial and we may conclude that $$P(x)=x^5-(x-1)^5.$$

In fact we have that $$ \eqalign{ & \sum\limits_{k = 1}^n {P(k)} = n^{\,5} \quad \left| {\;\left( {1 \le } \right)n \in N} \right.\quad \Rightarrow \cr & \Rightarrow \quad \left\{ \matrix{ P(1) = 1 \hfill \cr \sum\limits_{k = 1}^{n + 1} {P(k)} - \sum\limits_{k = 1}^n {P(k)} = P(n + 1) = \left( {n + 1} \right)^{\,5} - n^{\,5} \hfill \cr} \right.\quad \Rightarrow \cr & \Rightarrow \quad P(n) = n^{\,5} - \left( {n - 1} \right)^{\,5} \quad \left| {\;\left( {1 \le } \right)n \in N} \right. \cr} $$

To solve your perplexity about $P(n)$ being of degree $4$ wrt to the sum giving a degree of $5$
consider that the sum of a polynomial with variable upper bound produce the same effect as the integral: i.e. it raises the degree by $1$.