Let's get back to the creating an app package and uploading part, as that is where I experienced some difficulties.

I had an locally working Universal Windows Platform game, a Microsoft account and Visual Studio Community 2015.

So per instructions you'd right click on your app in Solution Explorer, choose "Store->Create App Packages". Sounds easy, but didn't work. A dialog came up and showed an error about not being able to connect to my account and Visual Studio actually hung.
I had no idea why that part wouldn't work. Restarted Visual Studio, updated the SDK, rebooted, nothing changed. Than, after reading that dialog more focused, it dawned to me. A plain Microsoft account does not suffice, you need an actual developer account. This is two different things!

So off on developer.microsoft.com I created an account, paid the required license fee (something akin to 9 Euros) and voila, the dialog would suddenly work!

From here on I created the App Packages, which required a few more settings to enter. Here's another stumbling block I encountered: You need to provide a few logos/badges/icons. All in a gazillion formats, scaled 100% and 200%. Here I wish you could provide one image and have the other formats auto-created. From there you could still polish up or replace the uglier ones. If you ever want to modify the settings of your app either double click "Package.appxmanifest" or via menu Project->Store->Edit App Manifest"

Finally my app packages compiled successfully (per default you'll have x86, x64 and ARM). Then came the Application Verifier...

The Application verifier will run your app several times, check your icons/badges and after a few minutes return a result of either "failed" or "passed". The link behind that will show you the details why something failed. The listed errors are also linked to a web site explaining the messages in detail.
For example one of my failures was explained as "The first pixel of the icon is not 0xffffffff or some other value)". What that message actually means: Those particular icons are supposed to be two colors only. You'd expect that to be shown when you select that image in the app properties.

Next time more details about the uploading part.