Solution:

The units digit of $2^n$ cycles $2, 4, 8, 6,$ so $2^{2008}$ ends in $6.$ Also $2008^2$ ends in $4.$

Thus $k$ ends in $0,$ so $k^2$ ends in $0.$

Both $2008^2$ and $2^{2008}$ are multiples of $4,$ so $k \equiv 0 \pmod 4,$ which makes $2^k$ end in $6.$

The units digit of $k^2 + 2^k$ is $0 + 6 = 6.$

Thus, the correct answer is D.