Your safest bet is to start over and treat everything in and on that computer as suspect if you think it's compromised. There are intermediary steps that are less drastic. Things like pulling the HD, mounting it on a known safe PC, and running a scan on the drive from that PC (don't run anything from the HD). Or burning a bootable DVD to check the computer (do this from a known safe computer)

Blizzard may be able to provide information as to how things happened that will help you understand the likelihood of your computer being compromised. I'd ask if they can tell you anything about how the authenticator was removed, dates, times, methods that they see from their end.

You can also always run a scan from the questionable PC with the questionable OS running. You'll have to decide if you trust the results or not. The usual advice about changing your passwords, at least battle.net/email attached to battle.net/any others that match applies.