Why do springs have a linear relationship? Why does:
F = k*(change in position)
Why can't the relationship be quadratic or higher ordered?
 A: It's an approximation motivated by calculus. Since by definition force is $0$ in the equilibrium position we label as $x=0$, the lowest-order approximation of $F$ as a Taylor series of $x$ is of the form $F=-kx$, unless $k=0$. (The sign indicates a force opposing the perturbation from a stable equilibrium with $k>0$.) Equivalently, the energy stored relative to equilibrium is, to lowest order, $\tfrac12kx^2$. (Since energy needs to be minimal in the stable equilibrium $x=0$, a quadratic force wouldn't work; maybe a cubic one would, but that requires two coincidentally zero coefficients, so forget it.)
Of course, these approximations work best for small $|x|$. It's a bit like a pendulum's small-angle approximation. In real life, the relationship is far from being linear at large $x$; we call this behavior anharmonic. The above logic motivates adding a cubic (quartic) term to the force (potential). Eventually, the spring undergoes permanent damage at some finite $x$ and energy, and this changes their future relationship. This doesn't even require you to snap it in two. So what really happens depends on the history of the spring. This is an example of hysteresis.
A: Springs do not always follow Hooke's law.  Hooke's law is a very good law, and it handles a lot of cases, but it's not The Law.
As J.G. points out in his answer, Hooke's law can be seen as an approximation that's good for small changes.  As it turns out, for the way springs deform, its a very good law because springs tend to deform in a "small change" way... every part of the spring deforms just a little.  Hooke got his name on the law because enough springs are close enough to this ideal linear behavior that it's useful.

All models are wrong; some are useful.

There are many cases where Hooke's law doesn't apply.  Its very common for suspension springs to not follow Hooke's law.  They're designed that way to create a smoother ride while still protecting against bottoming out.  If you look at a leaf spring on a truck or a train, they are designed to engage more and more linear spring elements to create an overall behavior which is closer to a square law.
