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
Here is a combinatorial proof. Suppose there are $n$ people, and I want to give them jobs. There are $3$ jobs, let's give them numbers $1,2,3$. Jobs number $1$ and $2$ can be done either at day time or night time, while job number $3$ can only be done at night. I don't care how many people will be at each job, but I want exactly $r$ people to work at day time. So how many options do I have to make such choice? First, I need to choose $r$ people who will work at day. Then for each one of them I need to give either job $1$ or job $2$, so it is $2$ options for each. Finally, for each of the $n-r$ people who will work at night I have three options: to give him either job $1$, job $2$ or job $3$. So the number of options is $\binom{n}{r}2^r3^{n-r}$.
Now let's compute the number of options in a different way. Suppose I want $k$ to be the number of people who will work at either job $1$ or job $2$. Note that $k\geq r$, because all $r$ people who will work at day are counted here. So I have to choose $k$ people out of $n$, the ones who will work either at job $1$ or $2$. Then from these $k$ people I have to choose the $r$ who will work at day time, the others will work at night. Finally, for each of these $k$ people I have two options: to give him job $1$ or to give him job $2$. Note that I don't have to choose anything else-the remaining $n-k$ people are exactly the ones who will do job $3$, and they will obviously do it at night time. And now we sum over the possible values of $k$, and get $\sum_{k=r}^n\binom{n}{k}\binom{k}{r}2^k$.