Do you need to supply higher voltage to a solenoid if using a flyback diode

That's not a flyback diode. It's a body diode. Different thing, different function, different connection.

Also, is the GND from the 5V regulator also going to the Arduino board?

This once more proves the importance of posting a schematic that accurately represents the circuit as built.