Make sure you bring your headset in pairing mode. You sead hear voice like' paring enabled such for the blutooth 'Now I have some doubt on your headset.Try to connect any other bluetooth headset (if you are having or your friend's) with your phone.I can definitely say that another one will connect.
You have to clear these doubts