I had been trying for days then finally got it to work. Here is what I did:
Press & hold select for 5 sec
Press & hold both select & play for 5 sec
Unplug fire tv stick from both tv and power and leave it alone for 5 mins
Plug it back in, go to settings using mobile app and then add new remote. Press & hold home for 10 sec.
At this point Fire tv finally found my remote and paired with it.