Arduino power and networking over cat6
In general, higher voltage means lower loss, so you do want to run highest economical voltage (but not more than 48V, this will be dangerous). I also recommending running a single voltage, but using two wires -- for example, orange/or-white for (+) and blue/blue-white for (-). This just makes wiring  easier, and significantly decreases the chances of microcontrollers spontaneously rebooting due to interference or ground loops.

First, lets see if you can use 12V. 20 ft of 23 AWG cable will have the resistance 0.4 ohm (assuming 20 ohm/1000 ft, and two wires in parallel for gnd and Vcc). At 0.6A, you will lose 0.24V, which solenoids are not going to notice. If you run 5 solenoid valves at once using a single cable, they will draw 3A total, and a cable will will drop 1.2 volt, still enough to energize the solenoids. So yes, looks like we can run 12V only.

Note that if you needed more power, you would have to go to 24V or 48V, and have 12V regulator in each box.

Now to get 5V, you can use linear or switching regulator. The advantages of linear regulator is that it is simple and already present on some arduinos ( not on pro micro). At 45mA, it will waste 0.3W, which is not a lot and easily dissipated. However, given that switching 5V regulators are less than $2 each on ebay, I highly recommend you just buy a dozen of them and use them everywhere.