In statusbar, long press on 'mobile data' and then 'mobile networks' menu will open. Go to 'network mode'. It should be set to 'auto connect'.
Some people use 'WCDMA/3G/UMTS only' which limits the connectivity when 3G signals are low and your phone cannot go to 2G mode to maintain signal strength, which causes low signals.
I think that's the issue, or maybe there is low signals in that area.
Your old Nokia is 2G only, and i think you set your S4 to 3G only. In auto connect mode, it is 2G+3G both which is set according to signal strength.
It should always be set to 'auto connect'.