Die Kaspersky Rescue CD ist schon mal ein guter Ansatz.
Was hast du denn für ein Antiviren Programm auf den PC? Ein sehr gutes kostenloses Tool um Schädlinge aufzuspüren ist Malwarebytes Anti-Malware:
http://www.chip.de/downloads/Malwarebytes-Anti-Malware_27322637.html
Tool installieren, einen kompletten scann und evtl. Funde in die Quarantäne. Poste uns das Ergebnis vom Logfile.
Hat es einen Grund, das du Avira PC Cleaner eingesetzt hast? Dieses Programm kenne ich persönlich nicht. Selber habe ich schon oft Malwarebytes und ADW Cleaner auf diversen Computer eingesetzt und oft wurden diese Programme fündig. Kann ich nur empfehlen.
Interessant wäre es natürlich zu wissen, was dein Avira PC Cleaner gefunden hat. Gibt es Log Dateien von den Funden?