The spring stretches mainly by torsion (twisting) of the wire of which it is made. At stresses below the elastic limit this occurs by small, temporary changes in the separations of the atoms. Beyond the elastic limit, planes of atoms in the metal start to slip a finite distance over each other. This is an irreversible process. [Energy would have to be supplied to return the planes to their old positions, even if this were practicable. Put simply, once the slip has occurred, the atoms in one plane are perfectly happy with their new neighbours!] The slipping increases the random vibrational energy of the atoms, rather than the elastic potential energy.
[The increase in random thermal energy is only temporary as there will be a flow of heat to the surroundings until the spring's temperature has fallen to that of the surroundings.]