If you take the averaged sum over all choices of signs $$\frac{1}{2^k} \sum_{\varepsilon_i = \pm 1} (\varepsilon_1x_1 + \cdots + \varepsilon_kx_k)^r$$ we see that only the terms with even exponents survive. If we place all $x_i=1$ we get the quantity that you are interested in. This is more explicitly equal to $$ \frac{1}{2^k} \left( \sum_{m=0}^k {k \choose m} (k-2m)^r \right).$$
– Gjergji Zaimi, Aug 24 at 0:45
The sum is the coefficient of $x^r/r!$ in $\cosh^kx$.
– Ira Gessel, Aug 24 at 3:53
– Max Alekseyev Aug 24 at 9:38
