I have an old Samsung S4 Active with android 4.2? I think. Same problem... all of a sudden Edge 520 and phone were paired but they will never connect.
I tried restarting the devices, forgetting the bluetooth pairing and doing it again, did not help.
What solved my problem was REINSTALLING Garmin Connect on my phone!
I used to have this problem with my old OnePlus One as well as my OnePlus 6 back when I had Android 9. Occasionally my ride would sync soon after I saved my ride on my Edge 520 but often I would have to restart my Edge 520 and occasionally I would have to restart my phone.
The way I found to fix this was to turn off Battery Optimization for the Garmin Connect app. After that change Garmin Connect would upload my rides almost immediately after saving the ride on my Edge 520 every time. There was no noticeable additional battery draw either.
The problem is gone on Android 10, I just leave the app set to Intelligent Control under Battery settings and all is good.
I had an issue with auto upload, Garmin technical support were useless in helping me to resolve the problem, I resolved the issue myself by removing my 520 from Garmin Connect and my smartphone because I could not see BT_Edge 520 on my phones list of bluetooth devices, BLE_Edge 520 was the only one I could see, I then began the pairing process again on my smartphone and GC and thankfully it has resolved the issue.