Yeah, I've yet to find any reasonable way to do this. I've had my Gear S3 paired to my S7 Edge, S8+, and Note 8, and each time I've had to do what amounts to a soft factory reset. Indeed, this is precisely what happens when you use the "connect to a new phone" function in settings. I can understand certain data like Samsung Pay cards being wiped out for security reasons. But I don't understand the rationale of having to reset your watch every time it connects to a new phone.