That there is no output start-up spike with the preregulator in place will be because the soft-start of the LM5118 adds tens of milliseconds to the time allowed for the bias to come up and actively control the gate of Q1. That's a pretty reasonable way to have a more controlled start. But let's set that aside to look at some of the other things that can happen during start up.
Start-up power sequencing is always a big concern with any power supply. Things can get quite involved, making sure that proper bias is present at the right time. Here are some common causes of overshoot on start up, in rough order of prevalence:
Integrator wind up. A precharge occurs on the integrator capacitor at start, causing a hard start.
Uncontrolled start of \$V_{\text{Ref}}\$. A unit step start of \$V_{\text{Ref}}\$ can cause an overshoot of output voltage.
Local bias voltage coming up late, or unbalanced start. Unbalanced start of bias can happen when there is bipolar bias voltage. Either the positive or negative output can come up first, in which case the output can rail.
Lack of termination at startup. If the output is unloaded at start, the output can overshoot and stay at an excessive level for an extended period.
All of these causes should be checked. Integrator wind up and controlled start of \$V_{\text{Ref}}\$ always have to be managed, and will get further attention here. Local bias sequencing and balance can take many forms and is hard to say much about specifically, but now that the local bias schematic has been added to the question, it is somewhat doubtful that any imbalance or delay would be severe enough to cause overshoot. Lack of termination is usually not a significant factor in a linear supply, but could make any existing overshoot more severe.
Integrator Wind Up
Without an active loop, such as under start up conditions, an integrator capacitor will always become excessively charged. High gain and any offset voltage or input bias currents of the OpAmp will combine to make this so. Then when the loop becomes active, the error amplifier is railed and the supply output overshoots. All practical integrator circuits used in power supplies have some means added to constrain charge up of the integrator capacitor. Quite common is placing a diode in parallel with the capacitor.
Here, \$D_{\text{Lim}}\$ is configured such that if the output of the amplifier should normally be higher than \$V_{\text{Ref}}\$, the amplifier will behave as an integrator. But, for output voltages lower than \$V_{\text{Ref}}\$ no excess charge up of \$C_9\$ will occur and the amplifier will only have unity gain. So, the amplifier can not end up railed to the negative bias voltage. No or minimal overshoot. In the case that amplifier output should be lower than \$V_{\text{Ref}}\$ during normal loop operation, \$D_{\text{Lim}}\$ connection can be reversed to prevent railing to the positive bias supply rail.
Sometimes using a diode is not restrictive enough, especially if \$V_{\text{Ref}}\$ is adjustable over a wide range. In this case a normally closed single pole single throw (NC SPST) analog switch can be used in place of \$D_{\text{Lim}}\$ to make the error amplifier have unity or some proportional gain during start up. At the proper time the analog switch is opened and the error amplifier becomes an integrator again. No overshoot.
Uncontrolled Start of \$V_{\text{Ref}}\$
An abrupt step in \$V_{\text{Ref}}\$ can cause overshoot or ringing at the output. Although this happens a lot at start up, it's not strictly a start up problem. A control loop with inadequate phase margin, anything less than about 68 degrees, will overshoot or ring with a step of \$V_{\text{Ref}}\$. Best way to handle this in general is to design the loop to have adequate phase margin. Best practice at start up is to initiate start with \$V_{\text{Ref}}\$ at zero setting and then ramp to the desired setting over a period of milliseconds.
Note: Initially it appeared that overshoot cause could be delay of local bias. Here is a test to verify and a possible solution offered.
Since it is crucial with this power stage to have active pull-down on Q1-G to maintain control of Q1-S, a crude pre-bias could be applied to Q3-B. A 50kOhm resistor, here shown as \$R_{\text{ff}}\$, could be connected from Q3-B to Q1-D. When voltage appears at Q1-D, Q3 would be turned on actively pulling down Q1-G. To make this work, D6 and D7 would have to be turned around, anodes tied together and R8, and D7-C to IC1A-1, and D6-C to IC2A-1 to allow Q3-B to be pulled down during regulation. This might be the simplest thing to do.
When \$R_{\text{ff}}\$ is not present, ripple rejection of the stage, open loop with \$D_7\$ cathode pulled low, is zero dB.
With \$R_{\text{ff}}\$ in place ripple rejection improved to 20dB. 50kOhm was chosen on a wim, and no effort was made to find a better value.
#3 is right out. The solenoids are designed for and expect 24VAC. Powering them from DC will probably burn the windings open in short order.
I'd go with #2, and as far as triggering the triacs go, use an optocoupler designed for triggerring triacs. There are many out there, you can even get them in zero-crossing or non-zero crossing varieties. Depending on the load, you might get away with just an opto-coupler triac, without it driving a larger one, but I don't know what kind of load your solenoids are. Vishay makes the VO2223, which is rated for up to 900mA on the load side.
Best Answer
You don't give details of the output voltage of the supply or the required value of the 'regulated' voltage output so the following is a generic answer.
Assume the output (unloaded) is 12V and you require a 9V regulated voltage and a short circuit current of 70mA and you don't want to use a regulator IC.
First step is to fix a reference voltage.
A small current passes through the Zener (say 10mA.) If the Zener voltage is 9V6 then for the assumed values this means the resistor drops (12 - 9.6) = 2.4V and at 10 mA this gives 240R for its value. The Capacitor is there to smooth the voltage and has a value of 10 - 100uF (not critical)
The current available to take from the zener is too small to be used directly so we need to amplify it with a transistor.
The transistor drops about 0.6V between the base and emitter leaving 9V at the output. The problem is that if the output is short circuited it will destroy the transistor so we need to limit the current.
The second transistor is only turned on when the current flowing through the limit resistor produces the turn on voltage (0.6V)
For 70mA this will be 0.6/70 * 1000 = 8R6.
When this voltage is reached the second transistor shuts off the first transistor and the output voltage falls.
IC regulators contain much more sophisticated circuits and for a cost effective solution I would go for them every time.