The contractors' "...could have caused damage..." statement feels a bit off- he probably didn't bother to test them. Heating elements are pretty dumb things that also fairly easy to test with an ohm-meter (only with the power off.) Depending on it's power rating it should measure a resistance between 11-16 ohms. Even if/when a heating element is encrusted in scale & lime, if the power is still going in, it'll still be heating the water at the same rate. Only if the thing has been damaged to where contact is intermittent or the resistance has gone much higher than spec would it make sense to swap it out. Instructions on how test them yourself start on page 8 of
the manual.
An eroded/corroded dip tube at the cold input port that is no longer going all the way to the bottom of the tank can also shorten the shower time, since it's injecting cold water at mid-tank rather than at the bottom. It's hard to diagnose that problem until the dip tube is VERY short, when it seems as if the hot water runs out very quickly, but the recovery time is pretty short.
Easy DIY band-aids would be installing low-flow shower heads (or an in-line shower volume control valves by the shower heads), since lowering the gallons per minute extends the amount of time it takes for the hottest water to be depleted. A lot of old-school gusher shower heads run 4 gpm or more @ 80psi, and are still over 3 gpm @ 30 psi. There are some pretty good
1.5-2 gpm shower heads out there, if simply throttling back the flow with a volume control valve isn't satisfactory. It may be worth
bucket-testing the flow rate of the existing shower heads as a sanity check before making a showerhead swap, but
a control valve can reduce the flow at any shower head.
If there is a thermostatic mixing valve or tempering valve between the water heater and hot water distribution plumbing (now required by code in new construction, and whenever a water heater is replaced), you can crank the storage temperature of the tank higher, which will give it a higher heat storage capacity but also higher standby losses-which is still probably going to be OK for most electric water heaters, which have fairly low standby losses. If the hot water distribution plumbing isn't already insulated, insulating it with R3 or higher foam pipe insulation everywhere, including the first 5 feet or so of cold-water connected pipe, and the temperature & pressure relief outflow pipe for good measure.
If there isn't a thermostatic mixing valve or tempering valve in place, raising the temperature of the hot water is a hazard. Installing a thermostatic mixing valve is do-able as a DIY for handy people, but if your space is really cramped it could be a real PITA project to take on.