Keeping a consistent supply voltage while driving a solenoid from battery

There are several problems here.

Turning on the solenoids causes a significant short term drop on the supply voltage. The actual voltage level doesn't seem to be a problem, but the rapid dip is. The obvious fix is to make less of a dip with slower edges. Put a bulk capacitor accross the power input right where it enters the board, and put smaller caps near the relays right where they draw power. Pay attention to the loop current thru these caps, and the overall relay power currents accross the board. The problem you may really be having is ground bounce when the relays kick in due to bad ground design. It would be best of the relay return currents did not run across the main ground plane, but had a separate return to the main ground point at the power supply feed.

Problem two is that your low voltage supply is susceptible to fast transients on the input. Since you have lots of voltage headroom, a little filtering in front of the 7805s will slow down the edges to where the active circuitry in the 7805 can deal with then, and also take some of the heat load.

Problem three is that the linear regulators are getting too hot. This is because they are dropping the difference from the power supply voltage to the 5 V logic supply times its current as heat. For example, let's say you need 100 mA at 5V. With 14 V input, the regulators are dropping 9 V, which times the current comes out to 900 mW. That's likely out of spec for a small surface mount part.

Adding larger regulators with heat sinks will be bulky and expensive. A better answer is to use a small buck regulator. Even if it is only 85% efficient (pretty low by today's standards), the same 100 mA at 5 V out will cause less than 100 mW dissipation. It can be small SMD parts without any special thermal considerations. One switcher should be good enough for all your 5 V needs.

If you need extra clean 5 V supplies, you can have the switcher make 5.6 V or so and use small low-dropout linear regulators at the point of usage. These won't get hot since they would only be dropping the 600 mV times the 5 V current. Put a small ferrite chip inductor followed by cap to ground in front of each LDO.

Another thing to do is to put a Schottky diode followed by a cap to ground in front of the switching regulator. This will prevent sudden drops in the input power voltage from forcing the input of the switcher low. The resulting transient will be slow enough to give the switcher a chance to deal with it properly.

Often a punch-through failure on the gate due to ESD can cause the gate to fail with some voltage on it leaking through from the body. If this is ESD damage, then handling the FET according to safe ESD practices will prevent future failures.

Keep the FETs in ESD safe packaging until needed. Use a wrist strap that's correctly grounded when handling the FETs. Do assembly on a bench with a grounded ESD mat.

Also, some newer FETs have gates that are only rated to 8V. Make sure your FET gate is rated for 12V operation.