It was very likely a combination of all that you said was done to remove McAfee....CCleaner, which truly is not a program generally used to do Uninstalls, it deletes LISTINGS so they aren't visible anymore but very often not the program files themselves, then System Restore. If it was removed, but System Restore was holding old files...well, using system restore brought some of those back but they likely are not listing in the correct place and the traces of those are not able to be found because they aren't listed where they are supposed to be listed and may not actually be called McAfee either, though they are recognized by both Combofix and DDS as McAfee based files. Using system restore to attempt to fix something very often makes it worse, mainly because it will not remove a program but often bring back parts of programs that were removed.

Is combofix not allowing you to run it or just giving a warning?

Delete the old combofix file and download a new one BUT you are going to have to rename it during the download process in order to try to fool the infection:
During the download, rename Combofix to Combo-Fix as follows:
When you get to the box that says Save File, click Save File. And when the box Save file as...opens then save it as Combo-Fix and save it to the Desktop.
Close EVERYTHING else, ALL browsers, everything.
Then double click on that Combo-fix icon to run it. If it warns about McAfee, see if you can just ignore it and go forward. If it will go ahead then let it run through to the end. It will prepare a log for you and save it here, "C:\Combo-Fix.txt"
Post back with that log.