If I were you, I'd get a larger UPS, use it to power your Linux-based NAS and your PC, but attach the communication to the NAS. Run apcupsd on the NAS, and set up the Windows client on your PC. I've run in this mode before, and it's worked great for me. apcupsd is going to give you a lot more control over what happens during an outage than any other program you're likely to find, plus, of the free ones mentioned in this thread, it's the only one that's going to let you shut down multiple computers.

Getting a computer to start back up on its own after a power failure is just making sure that when a failure does occur, that your computers OSes are shut down, but the power is still on. As long as your computers are set to turn on when they get power (usually a BIOS setting these days), they'll resume when the power comes back on. It's possible for this to fail if the power comes back on in the few seconds between OS shutdown and when the power would have gone off, but there's not much you can do about that. There's no software solution, either. It's hard for software to run on a shut-down computer.