The problem with WOL is that it only works if the PC is shutdown and never powered off. Once Power is removed and returned the WOL won't work. Well the machines I have WOL won't work after power loss! The NIC's forget they are configured to accept WOL packets.
WOL boardcast magic packets are limited to the subnet the machine is sitting on. WOL requires the MAC address and this not routable over the internet. So I'm not sure how you would do it over the Internet, unless you a Raspberry Pi or similar to remotely issue WOL to your machines?
You could use as you say, the switch header on the PC motherboard connected to the GPIO of the Pi to start your machine.
Most PC's BIOS support three return of power options: 1. Stay off, 2. Return to Previous State, 3. Power On.
If want to keep it simple and not use a Pi and relay have look at this
http://uk.tp-link.com/products/details/cat-5258_HS100.html, it is on sale for about £30 in the UK. But you would still have to set the BIOS Power On option to 3. Power on after power failure on your machine.