I had Success with my S4 M919 on 4.4.2 NB4 modem As instructions state - odin back to MDL modem followed instructions listed, run regionlock away v1.3 [ROOT], phone restarted. Powered back off and started in Download mode and odin back to NB4 modem. No problems at all with AT&T or Straight Talk with AT&T SIM cards.
I use Odin3 v1.85 myself, I believe if you use a newer version (Odin3 v3.09) select "CP" instead of "Phone" to flash the modem. Correct me if I am wrong. Just for anyone who might question where is "Phone" on Odin3 v3.09
Yes I am Rooted used Towel Root.