(This post is inspired by "Is every $\mathbb{N}$ representable as $\sum\limits_{k=1}^{n} \pm k^3$"? My question is at the end.)
The problem of whether every natural number $N$ is,
$$N=\sum_{k=1}^n \pm k^p$$
in an infinite number of ways may be reduced to finding polynomial identities and checking a finite number of cases. (The background can be found in Dumitrescu and Xu's paper, but the identities here are new.)
For $p=5$, it can be shown this reduces to merely checking all integers $0\leq N<240$.
Details:
$\color{blue}{\text{I.}\;p = 3:}$
$$\sum_{n=1}^{10}s_n\big(x+n)^3-\sum_{n=1}^{10}s_{11-n}\big(x+n+10\big)^3 = 6\tag1$$
for the ten $s_n = 1, -1, -1, 1, -1, 1, -1, 1, 1, 1$.
As the paper points out, what remains is to show that all $0\leq N<6$ is a sum of cubes, which is indeed the case.
Note: This is more symmetrical and uses only $20$ addends, whereas the paper uses $28$ addends.
$\color{blue}{\text{II.}\;p = 4:}$
$$\sum_{n=1}^{20}a_n\big(x+n)^4+\sum_{n=1}^{20}a_{21-n}\big(x+n+20\big)^4 = 192$$
where $a_n =-1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, 1$.
$$\sum_{n=1}^{20}b_n\big(x+n)^4+\sum_{n=1}^{20}b_{21-n}\big(x+n+20\big)^4 = 480$$
where $b_n =-1, 1, 1, -1, 1, -1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, -1, 1$.
Since $\text{GCD}(192,\,480) = 96$, we can combine these two into one with sum $96$.
Let $\alpha=-2,\beta=1$, and $192\alpha+480\beta=96(2\alpha+5\beta)=96$, so we use the first sequence ${2\times,}$ and subtract it with the second sequence $1\times,$ to get,
$$\sum_{n=1}^{120}c_n(x+n)^4 = 96\tag2$$
where $c_n = \text{-Flatten[{a, Reverse[a], a, Reverse[a], -b, -Reverse[b]}]}$, in Mathematica.
Note: This uses only $(40\times2)+(40\times1)=120$ addends, whereas the paper uses $136$. (The authors then show that all $0\leq N<96$ can be decomposed into fourth powers.)
$\color{blue}{\text{III.}\;p = 5:}$
$$\sum_{n=1}^{20}u_n\big(x+n)^5-\sum_{n=1}^{20}u_{21-n}\big(x+n+20\big)^5 = 1668000$$
where $u_n = -1, -1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1$.
$$\sum_{n=1}^{24}v_n\big(x+n)^5-\sum_{n=1}^{24}v_{25-n}\big(x+n+24\big)^5 = 1509120$$
where $v_n = 1, -1, -1,1, -1, -1,1,1,1, -1, 1, 1,1,-1, -1, -1, -1,1, -1,-1,1,1,-1, 1$.
Since $\text{GCD}(1668000,\,1509120) = 480$, we can also combine these.
Let $\alpha=19,\beta=-21$, and $1668000\alpha + 1509120\beta=480 (3475\alpha + 3144\beta) =480$, so we use the first sequence $19\times,$ and subtract it with the second sequence $21\times,$ to get,
$$\sum_{n=1}^{1768}w_n(x+n)^5 = 480\tag3$$
where $(40\times19) + (48\times21)=1768$. (The explicit sequence $w_n$ is too tedious to include.)
Note: The very first version of this post had an identity for $p=5$ with more than $70000$ addends. But it can be reduced to just $168$ given explicitly here.
Question: For the remaining integers, anyone has an efficient computer code to show that,
$$N=\sum\limits_{k=1}^n \pm k^5,\quad\text{where}\; 0\leq N<240$$
is indeed the case? (P.S. Since it involves odd powers, one can reduce the range to $0\leq N<240$ as R. Millikan points out in this related question.)
Note: The paper does not deal with $p=5$.
Here's a solution for general $p$:
For general $p$, we only have to check numbers $0 \leq x < C_{p}$. But now actually it also suffices to check all the residue classes modulo $C_{p}$. Now the point is that \begin{eqnarray*} \sum_{n = 1}^{C_{p}^2}n^{p} &=& \sum_{n = 1}^{C_{p}}n^{p} + \sum_{n = C_{p} + 1}^{2C_{p}}n^{p} + \ldots + \sum_{n = (C_{p}-1)C_{p} + 1}^{C_{p}^2}n^{p} \\ &\equiv& \sum_{n = 1}^{C_{p}}n^{p} + \sum_{n = 1}^{C_{p}}n^{p} + \ldots + \sum_{n = 1}^{C_{p}}n^{p} \\ &\equiv & C_{p}\sum_{n = 1}^{C_{p}}n^{p} \\ &\equiv& 0 \mod C_{p} \end{eqnarray*} but now changing the first sign to minus we get $$ -1^p+2^p+3^p+\ldots + (C_{p}^2)^p \equiv -2 \mod C_p $$ Now for any even residues just continue like that; for $-2m$ just take $mC_{p}^2$ numbers such that the sign is minus if and only if $n \equiv 1 \mod C_{p}^2$. Finally for odd residues add one final power, which is of the form $(kC_{p}+1)^p \equiv 1 \mod C_{p}$.
This proves that any residue is attainable with at most $\frac{C_{p}^3}{2} + 1$ consecutive signed powers; using this it would take quite a lot of them to get numbers form $0$ to $C_p$, but it works.