Like Karol22, is had a similar problem with an Officejet Pro 8610 printing okay from a deskside computer (Win 10) but not from an HP Pavilion laptop (also Win 10). I followed your instructions (generally) and was finally successful:
1. I uninstalled the Officejet basic software (IRIS OCR and HP improvement programs remained in place). HP Support Assistant was installed - it remained in place.
2. I removed all references to the 8610 in printers, queues, and HP Support Assistant.
3. I changed the system configuration settings under the services tab to enable a clean boot.
4. After rebooting, I installed a new download of the OJ 8610 driver and software (OJ8610_198.exe). This installation found the correct printer, with the correct printer name and installed.
5. For the first time, I was able to "Print a Test Page".
6. I reset the System Configuration to enable Microsoft Services again and rebooted. I then reprinted a test page and general text document to prove the installation worked.
Thus, the installation was now successful. It appears that the most important step was the disabling of Microsoft Services (something that most users wouldn't know or may not be able to do), in order to remove any confilicting drivers or software. Your inclusion of "How to Perform a Clean Boot" and other references were keys to success here.
Fellow users: if you have a recalcitrant Officejet Pro 8610, these are the steps to success: (from RnRMusicMan's post)