Ok I got it, it was my mistake (didn't contact customer service).
Steps:
1) Update the firmware of you RX-V485. YOU NEED TO DO THIS, otherwise the "Device Search" option won't appear.
2) Lets say you have your TV connected on input HDMI1. While on HDMI1 press and hold the power button on your headphones until you hear the "Bluetooth pairing" prompt.
3) On your remote control press: Setup>Bluetooth>Device Search
4) When your headphones appear, select them by pressing Enter. Done.
My silly mistake was thinking you needed to use the Bluetooth button on your remote control.