Windows 10 apps don't work on brand new Dell computer and laptop

No issue on domain-connected Lenovo machines.  Did you turn UAC OFF for any reason?

brand new Dell computer and laptop.   <-- Did you ask Dell Support (as warranty applies here)?

John, did not speak to Dell yet as I kinda can see that they will tell me about re-installing Windows unless they are aware of the issue.
I did it with UAC on and off.

Do you know if there is support from Microsoft for newly bought operating systems?

Greg, I am going onsite to see Dell OptiPlex tomorrow so will give it a go and will report back.

So far as I know it is not a Windows problem but a Dell problem. Please start with Dell

Tried permissions as suggested by Greg and it was just like you described (this was under not fully working profile). However, I did not try re-installing apps after that as the user required his computer.

Contacted Dell and was sent this link with the solution:
http://www.dell.com/support/article/uk/en/ukbsdt1/sln298640/issue-starting-using-built-in-windows-10-component?lang=en 
Solution.
1.Open a Command window started as Administrator by typing: cmd on the search bar then right-clicking or tap and hold then select Run as Administrator from the drop down list.
2.Repair corruption using the following command:
dism /online /cleanup-image /restorehealth then press the Enter key.
3.If this command reports problems that cannot be fixed, stop here. There may be a memory or hard drive issue. Windows needs to be Reset to repair the damage.
4.Run this command next:
Sfc /scannow then press the Enter key.
5.As above, if this reports problems that cannot be fixed, stop here. There may be a memory or hard drive issue. Windows needs to be Reset to repair the damage.
6.Now run these two commands:
PowerShell -ExecutionPolicy Unrestricted then press the Enter key.
Get-AppXPackage -AllUsers |Where-Object {$_.InstallLocation -like "*SystemApps*"} | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}then press the Enter key.
7.Watch for red errors, which could indicate a problem which cannot be repaired. If you see errors, Windows needs to be reset to repair the damage.

I am planning to do that next week as I am away and do not want to make it worse and not to be able to fix it remotely.

Tried everything suggested, but the issue was still there. Decided to "Refresh" Windows. It finished on Friday evening successfully, so I will be setting up the laptop with user accounts and software on Monday and will let you know if everything is okay.

I will be honest that the best way to fix that is to do Reset and to not forget to fix the permissions after that as the first thing.
Also, Microsoft just released new version of Windows 10 so this may fix the issue.
And finally, I discovered that the permissions corruption is present on some of my Windows 10 computers which did not have this problem before (but they did not come with the same version 10 but the previous build and then had update applied).

Would you like me to test applying new Windows 10 update to the affected machine or shall I close this question here?

PS. Sorry for the delay, I was traveling and having trouble getting hold of affected machines.

Did you contact Dell?  Microsoft Windows Updates have not been an issue for me. Dell did release some patches so you should contact their support people.

I did not contact Della again but their last guide indicated that their may suggest "Windows needs to be reset to repair the damage."
I will install the latest built of Windows 10 tomorrow and will post the update.

Try a Windows 10 Repair Install on one of the machines to see if that makes a difference.

https://www.microsoft.com/en-us/software-download/windows10

Windows 10 is running, so click on the Download button (not Upgrade Button, select Open (Run) but NOT Save. Allow the program to run. Allow drivers to update. Then select Keep Everything

Updating Windows to the latest build did not fix the issue. Following the steps in the solution as fixing the Apps folder permission as suggested does the trick.