Let $B_N=\{(x_1,...,x_{k+1})\in\mathbb{Z}^{k+1}:1\leq x_1<x_2<\cdots<x_{k+1}\leq N\}$ and $A_N=\{P(x_1)+\cdots +P(x_{k+1}):(x_1,...,x_{k+1})\in B_N\}$. Clearly $|B_N|=\binom{N}{k+1}$, whereas $|A_N|\in O(N^k)$, since each of the polynomials is of degree $k$. Since $\lim_{N\rightarrow \infty}\frac{|B_N|}{|A_N|}=\infty$, it follows that for some $N$ there exist two elements of $B_N$ which map to the same sum of polynomials. If $y_1,...,y_{k+1-d}$ are the common entries of the two tuples and $x_1,...,x_d$ and $x_{d+1},...,x_{2d}$ are the entries not in common, it follows that $$P(y_1)+\cdots +P(y_{k+1-d})+P(x_1)+\cdots +P(x_d)=P(y_1)+\cdots +P(y_{k+1-d})+P(x_{d+1})+\cdots +P(x_{2d})$$$$\implies P(x_1)+\cdots +P(x_d)=P(x_{d+1})+\cdots +P(x_{2d})$$This satisfies the desired equality, and clearly satisfies $d\leq k+1$, so we are done. Remark: the idea is almost the same as ITAMO 2014/5 The extra problem looks much harder, but for $d=k=2$ it almost looks to be true, because for every polynomial of the form $ax^2+bx+c$ the problem can be reconducted to $(2ax_1+b)^2+(2ax_2+b)^2=(2ax_3+b)^2+(2ax_4+b)^2$. I'm not sure if this is true but the similar $x_1^2+x_2^2=x_3^2+x_4^2$ is true, so it is probable in this case as well.

Very nice proof! I thought of this problem myself, inspired by RMM 2017 P2, but it seems to me that I could only prove a bound of $d\le k+1$ purely by counting arguments. For $d\le k$, some deep number theory is probably in play, which I am not sure how to proceed.