Here's a combinatorial proof for $$\sum_{k=1}^n k^2 = \binom{n+1}{2} + 2 \binom{n+1}{3},$$ which is just another way of expressing the sum. Both sides count the number of ordered triples $(i,j,k)$ with $0 \leq i,j < k \leq n$.
For the left side, condition on the value of $k$. For each $k$, there are $k^2$ ways to choose $i$ and $j$ from the the set $\{0, 1, \ldots, k-1\}$.
For the right side, consider the cases $i=j$ and $i \neq j$ separately. If $i = j$, then there are $\binom{n+1}{2}$ such triples. This is because we just choose two numbers from $\{0, \ldots, n\}$; the smaller must be the value of $i$ and $j$ and the larger must be the value of $k$. If $i \neq j$, then there are $2\binom{n+1}{3}$ such triples, as we could have $i < j$ or $j < i$ for the smaller two numbers.
For $$\sum_{k=1}^n k^3 = \binom{n+1}{2}^2,$$
both sides count the number of ordered 4-tuples $(h,i,j,k)$ with $0 \leq h,i,j < k \leq n$.
For the left side, once again if we condition on the value of $k$ we see that there are $\sum_{k=1}^n k^3$ such 4-tuples.
For the right side, there is a bijection from these 4-tuples to ordered pairs of two-tuples $(x_1,x_2), (x_3,x_4)$ with $0 \leq x_1 < x_2 \leq n$ and $0 \leq x_3 < x_4 \leq n$. There are $\binom{n+1}{2}^2$ such pairs, so let's look at the bijection.
The bijection: If $h < i$, then map $(h,i,j,k)$ to $(h,i),(j,k)$. If $h > i$, then map $(h,i,j,k)$ to $(j,k), (i,h)$. If $h = i$, then map $(h,i,j,k)$ to $(i,k), (j,k)$. This mapping is reversible, as these three cases correspond to the cases where $x_2 < x_4$, $x_2 > x_4$, and $x_2 = x_4$.
(Both of these proofs are in Chapter 8 of
Proofs that Really Count, by Benjamin and Quinn. They give at least one other combinatorial proof for each of these identities as well.)
Best Answer
The captain of the pirate starship Free Enterprise finds $m$ Martians and $n$ Neptunians in a bar. In how many ways can she select a crew of $j$ creatures for a raid on Jupiter?
The right-hand side $\binom{m+n}{j}$ counts the number of ways to select $j$ creatures from the $m+n$ creatures available.
So does the left-hand side. For she could select $0$ Martians and $j$ Neptunians. This can be done in $\binom{m}{0}\binom{n}{j}$ ways.
Or else she could select $1$ Martian and $j-1$ Neptunians. This can be done in $\binom{m}{1}\binom{n}{j-1}$ ways.
Or else she could select $2$ Martians and $j-2$ Neptunians. This can be done in $\binom{m}{2}\binom{n}{j-2}$ ways.
And so on. Thus the number of ways to recruit $j$ creatures is given by the sum on the left-hand side.
Comment: The result, and the reasoning, remain correct even if, for example, $j>n$. All we need to do is to define $\binom{u}{v}$ to be $0$ if $u<v$.