Yesterday an official delineation of solution to this task appeared (PL). I am disappointed that it's much slower than above. However, it presents me a new point of view of the problem. In conjunction with it, my idea is quite nice.
Main thing in this proof is fact, that set of indecomposable numbers is finite. Accept this as a well-known fact, or if you don't want, look here.
Helpful in understanding, it may be observation, if $n$ isn't inter-grown, and $k(n) = x$ then $n + (x+1)^2$ isn't inter-grown.
Inter-grown
First observation should be, than $n = \sum_{i=1}^{x}{i^2}$ isn't inter-grown. $n$ uses all squares not larger than $x^2$, so if $n' > n$ it's impossible to present $n'$ using only lower, than $x^2$. Emphasize that $k(\sum_{i=1}^{x}{i^2}) = x$. Now we should take advantage of the observation from question. If $x$ is the smallest number, witch satisfies the inequality $\sum_{i=1}^{x} i^2 \geq n$, then $k(n) \geq x$. So, we can predicate, that $n$ is inter-grown, if $k(n) > x$.
Value of $k(n)$
Now, let's look at it from other side. Let $n' = \left(\sum_{i=1}^{x} i^2\right) - n$. In this case we can present $n$ as sum of different squares (not bigger than $x^2$) if and only if $n'$ isn't indecomposable. Simply subtract $\left(\sum_{i=1}^{x} i^2\right) - n'$, if $n'$ is indecomposable it's impossible. That's obvious. If $n'$ is indecomposable we have to check $n'' = \left(\sum_{i=1}^{x+1} i^2\right) - n$ in the same way. We need to check, until we find decomposable $n^{*}$. But, wait! The greatest indecomposable number is 128, so $(x+1)^2 > 128 \wedge n'' = n' + (x+1)^2$ guarantees that $n''$ is decomposable! So from sufficiently large $n$, $k(n)=x~~\dot{\vee}~~k(n) = x+1$.
It's not hard to see, if and only if $n'$ is indecomposable, $n$ is inter-grown.
Counting isn't hard too. As expected, we have to remember for small $n$, groups can overlap and we have to count it by computer. After we can just add 31 with each subsequent square. The last group not necessarily add 31, cause not all elements have to be in, but they occur on a regular relative position ($n' \in \lbrace 2, 3, 6, 7, 8, 11, 12, 15,..., 128\rbrace$, so it's obvious, why.) and it's really easy to count. I don't think I have to describe it.
Best Answer
Just to provide an answer synthesized out of the comments already posted, your best (read as easiest) approach to this kind of problem is to toy around with general patterns until something either clicks and you can write a clever proof or until you accidentally exhaust all possible cases.
In this particular problem, we can break down cases into the residue classes $\bmod 4$ in order to hunt for patterns:
1) If $n=2k+1$ then the decomposition $n=(k)+(k+1)$ satisfies our criterion since consecutive numbers are always coprime and $k\geq 3$.
2) If $n=4k$ then consider the decomposition $n=(2k-1)+(2k+1)$. Are these numbers coprime? We can no longer rely upon the general fact that consecutive numbers are coprime, since these are not consecutive. However, if two numbers differ by exactly $2$, what is the only prime factor that they can share? In general, if two numbers differ by $m$, what prime factors can they share? Finally, are we sure that these numbers are both greater than $1$?
I have basically given away the entire answer, but I didn't know how to discuss this phenomenon in any other way, so I leave the final details of the second case, and the entirety of the third case, to you.