Hold down the setup button for 10 seconds, or until the LED light on your sensor starts blinking orange from red, indicating that the sensor is reset and ready to pair again.
Start zigbee pairing on HE (don't be pressing the hue button during this stage)
By this I am assuming you are both referring to the button on top of the Hue bridge. I would add to this to make sure if you have any other Zigbee hubs that they are not setup to accept new pairing with devices, the motion sensor could be being snapped up by something else before HE has a chance.
I understood the OP to be referring to the actual sensor, as I was (sorry, should have been clearer). It seems like the OP was pressing the reset button on the sensor during the pair process which cause it not to pair as it would be continually resetting.