Do I need to include overhead when picking a power supply?
It is actually a complicated question. What you DON'T want to do is pad everything and end up with 2x or 3x more power than you need. On the other hand, sometimes you have to really read the fine print on a power supply to see if it puts out its rated power 24 hours a day 7 days a week, or if the rated power is only applicable in a room kept at 25C with airflow of 10m/s over the case. So take that as a homework assignment for you. Are there any footnotes about the power output on the power supply?
Also, just as far as you calculation goes, you have to factor in the efficiency of the 12V to 5V buck. So if each Pi really needs 12.5 W, and you choose a buck with an efficiency of 90%, then you need 40 * 12.5 / 0.9 = 556W at 12V. Your calculation assumed that the bucks were infinitely efficient. Note, I just made up the number for efficiency. You should do the calculation with the real efficiency from the buck you select.
On the other hand, is 12.5W just a short-term worst case that happens rarely? If so, maybe the 504 W calculation is already generously over-sized. So the fact that you didn't allow for losses in the buck, and maybe you have to derate it even a little more because it is going to be running in a warm area would be OK.
Regarding this part of it, what would help a lot would be if you could measure the ACTUAL 5V current consumed by one Pi doing the exact job that you expect the Pi's to be doing. Then you could multiply by 40 and get the true 5V current requirement. Then calculate the 5V power. Divide by efficiency to calculate the 12V power, and see if it is enough.
So, I think I gave you more questions than answers, but this is how I would think about a system design problem like this. By the way, it is a good idea to distribute the bulk power at 12V and down-convert to 5V at the device. Even though you will have some losses from the buck, it is much better than the nightmare of fat cable you would need to run to a 500 or 600W 5V supply to carry 100 to 120 Amps! If you can find readily available 48Vin buck converters, distributing the power at 48V is even better.