Try re-flashing the stock NC5 firmware using Odin. See this answer for instructions.
I have no idea why this is happening, but logically, I think that would have to work:
- You've already tried clearing the sources of security policies that disable settings (credential cache and device administrators). Also encryption, but you say the device was never encrypted.
- The problem persists after a wipe / factory reset, so it can't be caused by any of your apps or settings.
- I'm 99.999999999999% sure that this cannot possibly be caused by a hardware issue.
- I don't believe in black magic or possession by ghosts or demons.
So there's really nothing else left; whatever the problem is, it pretty much has to be caused by some problem with the firmware. Not only does that seem to be logically necessary, the circumstantial evidence heavily supports this theory: it happened when you upgraded the firmware, without (I infer) making any changes to the configuration or installing any apps.
And since the NC5 firmware isn't supposed to disable these settings, it's probable that either there's something wrong with the firmware you downloaded, or something went wrong with the upgrade process. So re-downloading from a reliable source (I've used the firmware linked above at least a dozen times, and never encountered a problem) and re-flashing should fix it.
One more thought:
Since I'm deducing that the firmware upgrade is the source of the problem, it might have something to do with the fact that you obtained the NC5 firmware from a source other than Verizon's OTA upgrade. I know that Verizon's OTA upgrades do more than just flash the firmware, as proven by this process for rooting an NG6 device (which I've used successfully) by temporarily downgrading to NC5, rooting, and then upgrading to NG6 from a non-OTA source.
Note that the instructions stress that it won't work if you leave out any of the steps, and the first step in the process is to take the OTA upgrade to NG6, then downgrade to NC5, root, and upgrade back to NG6 from a non-OTA source linked from the instructions. The fact that the author is providing his own link to the NG6 firmware, yet instructs you to start by accepting the OTA update and only use the non-OTA NG6 firmware he's providing in a later step, implies that while there's no problem using a non-OTA NG6 after you've done the OTA update, you'll have problems if you never accept the OTA update in the first place.
So, try re-flashing the previous firmware, then see if you can still get the NC5 OTA upgrade (or even the NG6 OTA upgrade). I strongly recommend taking a nandroid backup before trying this, because I've seen cases where downgrading the firmware can cause serious system malfunctions that I've only been able to remedy by doing a factory reset. Also, check whether the screen lock settings are enabled both before the OTA upgrade (but after the downgrade), and after the OTA upgrade.
I'm not 100% certain what the previous firmware was, but I'm pretty sure it was MDK, also available from the GalaxyS4Root page I linked at the top of this post.