I’m having the same issue. Every update requires me to reset my Apple Watch, re-download the watchOS beta profile, and then I’m able to download and install the software update. It’s very frustrating. I have no music, photos, mail, podcasts, or third party apps installed. I still don’t have enough storage to download the update until I reset my Apple Watch Series 3. According to the Beta 4 Release Notes, this is a known issue and the only way is to unpair your watch and perform the update when promoted to during setup.