Updated Galaxy Note 8 to 4.2.2: can't pair with Bluetooth devices afterwards
In fact, the problem was resolved by doing a second factory reset. Looks like it's wise to do the factory reset several times before declaring the problem. Do this before setting up your screens with your widgets etc. organised and make sure you have a backup.