I still think it is inductively easy, but I will admit there is some detail involved. I will sketch some reductions which should help you make a complete proof.
One reduction is straightforward: if any of the components $a_j$ add up to $k$ or less, pick one vector with those components, farm out the rest to other components, and now with one vector you have reduced the dimension of the problem by at least one, and you can finish with a claim of induction on n.
A variant on this is if one coordinate is smaller than another by a factor of (k-1) or more, use the vector (1,k-1) in the appropriate coordinates to zero out one coordinate and reduce the other one, again reducing the problem by one dimension.
Therefore, you need to handle the hard case, which is that the two smallest coordinates each have values greater than k, and also that we can't use (1,k-1) as above. Now the reduction is to show you can pick two vectors, a linear combination of which will zero out both coordinates, and now you reduce the dimension by 2 and refer to the inductive hypothesis.
So we now focus on a simpler problem: given a_1 and a_2 the smallest valued of the coordinates both greater than k, find integers c ,d , and e and find r,s and t and values x and y so that xc +yr =a_1, xd +ys = a_2, so that c+d+e=k=r+s+t and so that xe + st is not too big. If n is 4 or greater, we can likely manage the "not too big" portion by spreading e and t across several coordinates, turning these integers into integer vector components instead. So we will worry about the "not too big" condition some other time.
So to find c,d, r, and s, we will make c,d look like a scaled down version of a_1 , a_2 as best we can, take a large multiple of (c,d), and try to make up the rest with (r,s). Since we can't use (1,k-1) as above, that means (a_1,a_2) "looks like" a smaller vector, say (j,k-j), or (j,k-i). Essentially we subtract multiples of (j,k-j) from (a_1,a_2) until what remains has coordinates summing to at most k, and then we use these coordinates as our r and s, and let t take up the rest. If need be, we use parity and try to keep y=2 if we can't make y=1.
To do it carefully and make sure nothing goes wrong does require more work. However, the insight that you can reduce two dimensions at a time is one that I think helps make the proof more natural. If I can improve upon this to complete it before someone else does, I will.
Gerhard "Hand Waving To Get Airborne" Paseman, 2017.10.08.