re: Samsung Galaxy S4 missing icon from Favorites Tray
Yeah, I recall discussing this with someone else recently. The Australian ROMs don't allow the user to add or change anything in the Favorites Tray. I don't know why. When you disabled Messaging, that must have forced it out, but due to the ROM limitations, you can't add anything back.
The only thing I can suggest at this time is to go to the App Manager, select TouchWiz Home, and Clear Cache/Clear Data. This will wipe your homescreens clean, and presumably reset them to the original state. But do this with caution--I'm not sure if Clearing Data will also clear out the rest of the shortcuts from the Favorites Tray, which would then put you in a bigger bind.