I had exactly this problem but trying all the above suggestions did nothing. After a frustrating time trying and failing to communicate with SKY using their uselesss chat bot, I evenutally found a phone number to call. OK, it was an Indian call centre but, unusally, the person I got through to was actually quite useful and talked me through exactly the same steps (switching off, then on again, then 7&9 buttons, then 1&3 buttons while he could see my tv screen via my phone's camera. This time it worked (typical!). I got a list of TV brands rather then the 'pairing unsuccesful' mesasge. So if anyone else has this issue do not hesitate to dial [number removed]
Moderator note: phone number removed as these can often change
