Settings | Apps | Pokemon Go | Permissions
In here tap on Physical activity under Denied, and change it to allowed. you can also change all other items under denied to allowed if you like, but this is the one that worked for getting my eggs back on track.
Make sure Adventure Sync is turned on in Pokemon go. You may need to open Samsung Health from your phone, as it does not start tracking steps until you have allowed it to do so. I think I read somewhere that Samsung Health also has to have its storage permissions enabled, similar to how Pokemon Go needed Physical activity enabled. I had a hard time when I first got the Note20 Ultra, but it is working for me now.