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.
Best Answer
As you correctly noted, a step down converter is the right thing to use.
You'll notice that all bigger semiconductor manufacturers have tools on their website to help you design a step-down converter from e.g. 48 V to 5 V for the current your device needs (500mA, as you say).
However, if your PoE-injector is truly standards-compliant (far from all are), then there will be no 48V on the Ethernet port until the device signals it needs that (wikipedia)
In effect, it's probably easiest to just use one of the several "Power over Ethernet ICs"; generally, google is your friend, but let's directly link you to some common matching PSE product lines:
ST.com product category;
Texas Instruments product category;
Linear Technology's (now part of Analog Devices, Inc) product category, and one possible quick and dirty solution amongst many; [edited by My Other Head]
Note that PoE equipment typically is in the uncomfortable situation that they're trying to run power through communication lines. Since Ethernet uses differential signalling, you'll need typical ethernet signal transformers with a center tap on the network side if you want to use the cable for actual network, too:
simulate this circuit – Schematic created using CircuitLab
Now, if you don't actually plan on using the Ethernet as ... Ethernet a) you might be doing something strange and b) you might remove the magnetics (=transformers) and just terminate the ethernet lines with their specific impedance – 150Ω:
simulate this circuit
Note that the schematic above is but a dirty, inaccurate hack to make the ethernet port not see an open circuit at the end of your twisted pairs and interpret the port as unconnected.