Hint: Split the sum into "sum of $k$" minus "sum of max". Then draw the numbers to be added in a coordinate grid according to $x$ and $y$ values; I think you should consider even and odd values of $k$ separately.
For example, if $k=5$ you have to add the values
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
and from that subtract the sum of the values
4 3 3 2 2 2 1 1 2 3 0 1 2 3 4
Notice the mirror symmetry here:
4 3 3 2 2 2 1 1 2 3 0 1 2 3 4
You have the numbers 0 + 1 + 2 on the diagonal $y=x$, and then there are the numbers
4 3 3 2 2 1
which occur twice; moreover, 1+4=5 and 2+3=5, so they add up to three times 5 (times two).
Now try to generalize these observations to a general pattern. For odd $k$, say $k=2m+1$, I get the expression $ k^2 (k+1)/2 - (1+2k) m(m+1)/2. $
I'll leave the even case to you (or somebody else). :)