Just a bit of preliminary theory.
As you probably know, without any flyback diode, be it a rectifier or a Zener, you'll have a (theoretically infinite) kickback voltage from the inductor (valve coil, relay winding or whatever) whenever you try to interrupt its current abruptly. In reality the kickback won't be infinite because the spike will trigger any sort of nasty effects in the circuit it is connected: it will generate electric arcs, it will drive semiconductors in destructive breakdown, it will fry resistors or punch through capacitors dielectric, etc.
All this in the attempt of get rid of the energy stored in the inductor, which is
\$ E_L = \frac 1 2\, L\, I_L^2 \$
where \$I_L\$ is the instantaneous current at the time immediately before the (attempted) switch-off.
Putting a rectifier in parallel with the coil is the standard low-speed countermeasure, as you know. Assuming the diode can stand the inrush current pulse generated by the kickback, it will clamp the voltage across the coil to a safe ~0.7V. Why is it slow? Because at that voltage level (a diode forward drop) and with usual forward resistance values the power dissipated is low, so it takes more time to convert \$E_L\$ into heat.
Using a Zener is faster essentially because it allows the kickback voltage to rise more before clamping it. Of course the Zener voltage must be chosen not to be dangerous for the rest of the circuit. Since the clamp happens at higher voltage, and the breakdown dynamic resistance of a Zener may also be lower, the dissipated power is bigger, hence it takes less time to convert \$E_L\$ into heat.
If you wonder what happens when the clamp action ceases because the current is not enough to keep the Zener (or the clamp diode) in breakdown (conduction), well the answer is that it will probably oscillate, because the energy MUST be converted, since the power source of the coil has been cut-off, and the stored energy depends on the current in the coil. The coil won't "hold the energy" as a capacitor would do, because for that to be possible a current should flow into the coil itself. Therefore the remaining energy will find other ways to get converted: stray capacitance and leakage current of the diodes and parasitic capacitance of the coil itself (for example). It is sort of a non-ideal non-linear tank circuit, which will exhibit damped oscillations until the energy is completely converted into heat.
EDIT
(In response to a comment from @supercat)
Here's some results from a hastily conceived circuit simulation using LTspice showing the damped oscillation that may arise in a situation similar to the one described above.
The transient analysis produces the following plots:
If we zoom in the interesting parts we have:
In the following extremely zoomed-in plot you may notice the estimated frequency of the oscillations (I've enhanced the image to show where LTspice cursors are placed).
You must model the solenoid valve as a resistor (33\$\Omega\$ in your case) in series with an inductor. If you like you can include a bit of parallel capacitance, but the resistance is required.
Otherwise the simulated current after a long time will be limited only by the MOSFET (maybe to something like 30A) and the voltage will approach zero.
For the operation time of the valve, you can consult the data sheet. Normally they will specify it without a diode, so whatever time you get with the zener will be a bit longer. You can guess that the difference in the current through the coil will give you an idea of the operation time, but there is no guarantee that even if the coil current drops to 10% or 5% of normal that the mechanical parts will have moved in that time. Some valves are fairly complex ('pilot valves', for example that operate indirectly), and the inductance of electromechanical systems often varies significantly during operation.
Edit: Below is a PSPICE simulation I did with similar parameters to yours (I used a 1N4740 Zener and a PHD23NQ10T,118 MOSFET to save me time). Green trace is the gate drive signal (before the resistor), red is the MOSFET drain. As you can see the MOSFET drain rises to a peak voltage of around 24V.
In the below close-up, you can see where the bulk of the energy is dissipated and the ringing afterward. The violet trace is the coil current (scaled so you can see it on the same graph).
Best Answer
Can the zener affect the turn on time?
No. If it's not conducting, it's doing nothing. If it is conducting when you come to turn on, that means the relay has still some decaying current flowing, so it will turn on faster.
'The power driver circuit does not appear to have any components to eliminate back EMF'?
I agree, not on the face of it. However, follow your own RFP30... link to the data sheet. Look at figures 14 and 6. You will see that the FET itself is hardened against precisely the back EMF that an inductive load causes. Figure 6 shows that even starting at a die temperature of 150C, it will handle 3A for 1mS, 8A if it starts cool. During this time, the avalanche voltage across the device will be at least 60v. This is the voltage that's available for ramping down the solenoid current.
In order to use this information, you will need to know the inductance of your solenoid load, and the DC current it takes in operation. How long will it take to ramp down from its operating current at 60v? Will that fit inside the figure 6 lines? If it does, then there's no need for the protection components. To me, the RFP30... looks pretty tough.
But, you can use a diode and zener anyway, they won't do any harm. If you do, they must clamp before the 60v is reached, otherwise the FET will be protecting them, rather than the other way round! With a diode and zener, you'll have a lower turnoff voltage than using this FET alone. If you think you'd prefer a zener+diode because you don't want to do the sums on the FET, then don't forget, you should do the pulse-handling sums on the zener as well, how long can it conduct x current at 36v before overheating? You'll probably find the TO-220 FET is waaay harder than the zener!
The reason I went digging in the data sheet is the question 'how could SparkFun have a successful business selling switches that were going to break?'. Warning, not all FETs are this tough, and few BJTs are. Always assume you'll need back EMF protection until you've done the sums on the specific driver.