First, don't remove anything from DU000010, as we should never need to do so.
When you removed PRODID 7131 for Canadian Payroll from DB_Upgrade, DU000020 and DU000030, but had it installed, thus showing in the .set files when you launched Utilities, it then looked for CPY40205 and CPY30250 in any of the company databases for GP.
If it finds the CPY40205 table, it then looks for the PSupervisor column in CPY10100.
If it finds this column in CPY10100, along with CPY40205 table, it'll write a record into DB_Upgrade for PRODID 7131 and a version of 8.0.0.
If only the CPY40205 but not this column in CPY10100, then it gives a version of 7.50.0 for PRODID 7131.
If it doesn't find the CPY40205 table at all, it deems Canadian Payroll as not having been installed.
So, along with removing PRODID 7131 from the three system tables, you'd also have to drop CPY40205 and CPY30250 from every company database mentioned in the SY01500 table so that, when you launched GP Utilities again with CANPAY installed, it'd install that module anew at the version you're currently at, not attempt to upgrade it.
To upgrade to 18.2.xxxx from GP 2018, you need to be on a minimum of 18.0.0496, which at that build, Canadian Payroll would be at 18.0.0489.
If you were on 18.0.0628, Canadian Payroll would also be at that same build, 18.0.0628, so the "Product 7131 does not support upgrading from version 18.0.628" version error is interesting, as it should be at a valid version enough to upgrade to 18.2.xxxx.
Thanks