I've tried to connect my Pebble 2 HR (v 4.3) to Android for testing issues (I normally use it with iPhone), but no success. Tried older LG P990 with Android 4 and newer Asus ZenFone Go with Android 5. Still the same - installed Pebble App, enabled BT on phone and watches (i've deleted previous iPhone pairing profile). App started to seek for BT devices, found Pebble 2, watches asked me if I want to pair with that phone, I accepted it on watch and was waiting for pairing message on phone. Nothing happened. The app was still trying to pair with watches (even the watches showed the phone as connected) on and on. When I go to phone's Bluetooth settings, I saw Pebble there connected and paired. But the App still didn't finish the pairing.
I've tried to reboot both - phone and watches, turning BT on and off, nothing helped. Maybe I should do factory reset for watches as there are some apps and watchfaces installed and try it with 'clean shield'.
After switching back to iPhone, everything was OK, paired in few seconds and working. First time in my life I can say: Thank god for an iPhone.