This is why I said when you were planning to buy the S4, "skip the setup and to install the updates first". I was trying to prevent you from ending up in this situation. If you haven't unrooted yet, install Titanium Backup and start backing up apps you downloaded. There are XML options for backing up your Call Log and SMS/MMS. However you will have to set up your shortcuts and phone settings again.
Samsung Galaxy S® 4 MJA Rooted with CF Auto-Root Tutorial
HTC EVO Design 4G™ v4.0.3 Bootloader Unlocked & Rooted with HTC SuperTool v3
If it ain't broke, use a sledge hammer.