Hi, I also have this when I turn off Cellular Data on Galaxy S5 with latest Android. The Sync setting on mine was really difficult to find... but It was :
Open Contact app (the built in one, not an AT&T thing)
Go to the "..." menu on the upper right and choose Settings
From the next menu Choose Contacts
From the next menu choose Accounts
On this menu, choose the "..." menu on the upper right ((NOT the AT&T Address Book item on the menu, but the "More" button/menu on the upper right)
Uncheck "Auto sync data"
After I did this, I still got one more pop-up, but then it seemed to be gone after that.