I had the same issue. And finally fixed it by standing on the scale.
Scale wasn't uploading data to Connect, went through setup multiple times, could not get farther than wrench / Bluetooth icon. Removing / replacing the batteries or using the Reset button brought me back to Wrench / Bluetooth icon again, and Connect Mobile did not find scale.
The scale shows up in Bluetooth devices on the phone, but I couldn't get further, UNTIL I stood on the scale. Simply standing on the scale FIXED the issue..