I seriously doubt you had HP support. Everything you described is typical of the bogus tech support scams out there now that pretend to be from Microsoft, Dell, or any other well known brand name in an attempt to gain credibility and your trust to give them remote access to your computer. Then in the end, when the customer refuses to pay they either do damage to the OS or try to lock you out of it.
Typically, if you go to "Programs and Features" and sort the list by date installed, you will find the remote connection software installed and possibly other programs they installed on the date of scam. Simply uninstall it and that should stop them from gaining access to your computer.
You could alternatively, try doing a System Restore to a date previous to the scam date, but it's quite possible that they deleted all your restore points.
PS: If you could post any of the HP contact info that led you to this scam, we might be able to confirm that it's not actually HP.
--pete--