繋がりやすいと感じるのは、

Bluetooth詳細設定でペアリングしたあとに
ポケモンGO起動(起動後バックグラウンドでも大丈夫)
起動したら、タスクバーからBluetooth切断
しばらくして、Bluetooth入れる
ポケゴのマークタップで切断

かな

だいたい繋がりにくいときはBluetooth側でスマホが認識してない気がする