Device #1: It's a phone running on PfD, so CSC's confirmed getting the Samsung firmware (8.1.1) are ATO and BTU. ATO is Austrian CSC, BTU is English CSC. Try with those if you have them, the update maybe won't start rolling right away (usually it does), but wait for .... let's say 24 hours, check again and see what happens. neo158 has his ATIV S on ATO (if I am not mistaken) and got the 8.1.1 firmware. Make sure your PfD is checked ON.
Device #2: As you said, this is a phone not rolled PfD, so, CSC's that got 8.1.1 are
-
ATO - Austrian
-
BTU - British
-
DBT - German
-
ETL - Not sure about this, guess it's Slovakia (someone correct me if i am wrong)
-
NEE - Nordic (Sweden, Norway, Finland, etc)
-
PHN - I think is Netherland
-
TGY - probably Hong Kong
So, if you choose NEE and you don't have the new official update 8.1.1 in 24 hours, or you get the error, then try with changing Language and Region to Sweden and Swedish and check again. If that doesn't work, try any other CSC i mention above and report back if you get something positive