I suggest that you backup your phone using Kies or Samsung Switch on your computer then Factory reset it. After so, restore your phone from your backup. Please let meknow if it works. Thanks
Naexperience ko na rin to, if you have telegram and viber try to check your settings. May auto-download kase sa lahat ng narereceive mo, na nagiging reason bakit nafull ung storage.