Check for if I've picked the correct flyback and zener diodes for a solenoid valve driver
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.