1) Did you format the drive or roll-back using a restore point? If you formatted the drive you should be safe. If you rolled-back you MIGHT not be safe. In this case, it was a Win8 Reset so the computer should be safe. Run netstat to see what he computer is talking to. If it's talking to computers it shouldn't be you probably still have a problem (which might be solved via Windows Firewall).
2) Yes, you should probably run one of the "remove rootkit" programs. Malware bytes has a free one in beta that came up at the top of my Google Search. There are probably several other options. I've never used one so I can't personally vouch for them. Make sure Windows Firewall is setup and on. If netstat found any network activity that shouldn't be happening use the firewall to block it.