This is because the elastic force is not constant, it increases with extension.
That is correct
When force is pulled equally as hard at all positions,
It can't - you have to use more force as you displace further - that's the point of your first line
then there is squared the energy to be stored for double the pull-back distance, since this force will pull equally but travel twice as far.
The point is that the force is twice as big but travels the same distance, not the other way around.
How about this:
The elastic force is proportional with displacement. When you move a small distance, you initially have only a small force applied, so the work done (which becomes energy stored) is small. For the next unit of displacement, you start with the force you ended with, and then need to add more force; so you will have to do more work. If you draw a graph with the displacement along the horizontal axis and the force along the vertical axis, this graph looks like a triangle:
Of course the work done for increasing the distance is the displacement $\Delta x$ times the force $F$, indicated by the green shaded band. And as you keep displacing, you keep adding more bands. The total area of the triangle is of course the base ($x$) times the height $kx$ divided by two. Which proves the square law. I don't think you can get away without there being some math to prove it's a square (and not, for example, a cube) but the area-of-a-triangle argument is about as intuitive as I can make it.