Edit: When removing apps using Method 2, the apps may still show up in search but will close immediately when opened. To make them not show up, use Method 1 AFTER Method 2.
Edit 2: I am investigating an issue where I no longer have any access to any Windows Apps (including those I left) on my testing PC. Until then, please avoid using Method 2.
Method 1 - Remove for Existing Users using Administrative PowerShell
This method uses the PowerShell included in Windows 10 Pro to remove UWP apps, also known as Appx Packages, from pre-existing users on a computer.
First, run PowerShell as Administrator by searching for it in start and right clicking > Run as administrator.

Next, get a list of installed packages. To do this, we could type Get-AppxPackage
and read the million things that come up. Instead we will pipe it to the select command that only output's the packages short name, and then we will pipe it to the sort command to sort it alphabetically (just to look nice).
Get-AppxPackage | select name | sort name
This will produce an output like this:

For this example, we're going to delete all Bing apps (News, Sports, Weather, etc.) To do that, we again get the Appx Packages, but this time use wildcards to get them by name. We then pipe them to the Remove-AppxPackage
command, which is pretty self-explanatory.
Get-AppxPackage -name *Bing* | Remove-AppxPackage
PowerShell will display a deployment process, then give you back control. Getting the Appx Packages by name afterwards returns the following, void of all Bing apps:

To remove the Windows Store itself, do the same as above:
Get-AppxPackage -name *WindowsStore* | Remove-AppxPackage
These commands only remove apps from the current user. To remove them for all users on the computer, add the -allusers
flag like so:
Get-AppxPackage -allusers -name *Bing* | Remove-AppxPackage
Method 2 - Removing for All Users by Restricting Access to the WindowsApps Folder
This method is more complicated, but also more robust. We will be removing System's access from the folder where Windows Apps are installed to then deleting the ones we want gone, so they can't come back.
Windows Apps are are stored in C:\Program Files\WindowsApps\
. This is a hidden folder, so you'll have to show hidden folders first:

If you try to modify the folder properties right now, you won't be able to. This is because TrustedInstaller is the owner of the folder. To change this, right click on the folder, choose Properties, then go to the Security folder. Click the Advanced button.

The Owner:
field will either show TrustedInstaller
or Unable to display current owner
, as it does for me. Click Change next to Owner to change the owner.

Change the folder to a local or domain administrator (I did this using a domain administrator, but am using a local administrator for this tutorial). Make sure the Replace owner on subcontainers and objects
box is checked.

After this step, you will need to click OK and close all open dialogue and properties boxes for changes to take effect. Then, re-open folder properties and go to the security tab. You will now be able to change folder permissions. Click Edit.
Fully remove SYSTEM from the list of Groups and user names (this means it won't be able to reinstall apps back into the folder once they're gone). Next, add your local or domain administrator to the list and give yourself Full control.

Finally, go close all dialogue boxes and go into the WindowsApps folder. Select and delete whichever apps you like.

I would recommend KEEPING the .NET framework, as well as the Photos, Calculator, and windowscommunicationsapps
to ensure that the computer continues to work properly. I removed Zune video and music (the packages for Films & TV and Groove), but this left the computer without music and video playing programs, so you will have to install other programs if you want this functionality.
Final Remarks
Please note that this is a solution-in-progress, I have confirmed that it works across new users and restarts, but do not yet know if it is rock solid. Do NOT perform the steps above if you don't know what you're doing, as it can seriously break your computer if done wrong. I assume no responsibility for anything negative or problematic which may result as a result of following the above steps.
Feel free to add to this solution, as I hope it is one that other admins (or just annoyed users) can follow in the future.