Electrical analogies of mechanical elements such as springs, masses, and dash pots provide the answer. The "deep" connection is simply that the differential equations have the same form.
In electric circuit theory, the across variable is voltage while the through variable is current.
The analogous quantities in mechanics are force and velocity. Note that in both cases, the product of the across and through variables has the unit of power.
(An aside, sometimes it is convenient to use force and velocity as the across and through variables respectively while other times, it is more convenient to switch those roles.)
Now, assuming velocity is the through variable, velocity and electric current are analogous. Thus, displacement and electric charge are analogous.
For a spring, we have $f = kd \rightarrow d = \frac{1}{k}f$ while for a capacitor we have $Q = CV$.
For a mass, we have $f = ma = m\dot v $ while for an inductor we have $V = L \dot I$
Finally, for a dashpot, we have $f = Bv$ while for a resistor we have $V = RI$.
So, we have
$\frac{1}{k} \rightarrow C$
$m \rightarrow L$
$B \rightarrow R$
For a nice summary with examples, see this.
UPDATE: In another answer, RubenV questions the answer given above. His reasoning requires an update.
Alfred Centauri's answer is not correct. The analogy he mentions is
true, but it is irrelevant as it does not tell you anything about
components in series or in parallel.
In fact, it is relevant and it does tell you everything about components in series or in parallel. Let's review:
When two circuit elements are in parallel, the voltage across each is identical.
When two circuit elements are in series, the current through each is identical.
This is fundamental and must be kept in mind when moving to the mechanical analogy.
In the mechanical analogy where a spring is the mechanical analog of a capacitor:
force is the analog of voltage
velocity is the analog of current.
Keeping this in mind, consider two springs connected in mechanical parallel and note that the velocity (rate of change of displacement) for each spring is identical.
But recall, in this analogy, velocity is the analog of current. Thus, the equivalent electrical analogy is two capacitors in series (identical current).
In series, capacitance combines as so:
$\dfrac{1}{C_{eq}} = \dfrac{1}{C_1} + \dfrac{1}{C_2}$
With the spring analogy, $C \rightarrow \frac{1}{k}$ , this becomes:
$k_{eq} = k_1 + k_2$
The key point to take away from this is that mechanical parallel is, in this analogy, circuit series since, in mechanical parallel, the velocity (current) is the same, not the force (voltage).
For example, consider dash pots (resistors). Two dash pots in "parallel" combine like two resistors in series, i.e., the resistance to motion of two dash pots in "parallel" is greater then each individually.
Now, if the roles of the analogous variables are swapped, if force is like current and velocity is like voltage, then mechanical parallel is like circuit parallel. However, in this analogy, mass is like capacitance.
Best Answer
No, there is no reason why the stored energy should be the same in both cases. The only requirement is that the total force supplied by each system of springs is the same, because the two systems are supporting the same load, and each is in equilibrium.
The difference in stored energy does not 'go' anywhere because these are two separate cases. You are not converting one case into the other.
If you did start with the load supported by the springs in series and converted this to the load supported by the springs in parallel, the difference in elastic energy would not in fact equal the difference in gravitational PE of the load!
The tension in each spring would have to be reduced from $W$ to $\frac12 W$ where $W$ is the weight of the load, and the extension of each reduced from $x$ to $\frac12 x$. The elastic energy stored in a spring with tension $W$ and extension $x$ is $\frac12 W x$. The total elastic energy stored in the two springs is initially (ie in series) $2\times \frac12 Wx=Wx$ and finally (ie in parallel) $2\times \frac12 (\frac12 W)(\frac12 x)=\frac14 Wx$. The decrease in elastic PE is $\frac34 Wx$.
After the change from series to parallel, the springs initially supply a total upward force of $2W$ while the weight supplies a downward force of $W$. An additional downward external force is required, starting at $W$ and decreasing to $0$, to prevent the system from gaining kinetic energy as the tension is reduced. The work done against this external force equals the KE which the load would have acquired when it reached the equilibrium position had it been released. In that case it would have overshot the equilibrium position and oscillated indefinitely.
The work done on the load (average force x distance) by the two springs is $W\times (\frac12 x)=\frac12 Wx$, which is the increase in its gravitational PE. The work done against the external force is $(\frac12 W)(\frac12 x)=\frac14 Wx$. The total work done by the two springs is $\frac34 Wx$.
To summarise : the two springs lost total elastic energy $\frac34 Wx$ of which $\frac12 Wx$ increased the gravitational PE of the load while $\frac14 Wx$ was done against an external force.
See Mass dropped on a spring.