The HC-06 module (if you have the backplane with it too) has a state output...
This output toggles on and off when not paired and is solid on if it it...
So, you can write a routing that looks to see if this pin is on or off and waits to see if it's status changes.

Also, the pic can send an "AT" to the HC-06, if it receives an "OK" then the module is NOT paired...
However, if the module IS paired and an "AT" is sent then the "AT" is transmitted to the phone where the phone could be programmed to reply with it's own code... or not reply at all... In ether case the pic will know it's paired...