To upgrade from Windows 8 to Windows 8.1, you need to install all of the Windows 8 updates before you can install Windows 8.1 from the Windows Store.

Two ways to install updates

Update Center

1. Move your mouse to the top right of the screen
2. Select PC Settings
3. Select Windows Update

Windows 7 Style

1. Move your mouse to the top right of the screen
2. Select Search
3. Enter “Update”
4. Select Settings
5. Select “Install Optional Updates”
   1. 

Windows Updates Not Downloading

On one of the machines that I upgraded from Win8 to Win8.1, I found that the Windows Update Dialog was not progressing. I waited a while but the progress bar was stuck at 0%. See the screenshots above for an example of what I saw. There are two solutions to this problem:

Turn off metered connection

Some people has this issue and I think it comes from Windows 8 trying to play on more than just laptops. The solution is in Reddit Source 2 – Turn off metered connections but not for me and for some others, the data metered was in “Devices” and “Sync Settings”.

Wait it out, it will work eventually

You might have to wait upwards of an hour before you see the dialog change, but this seems to be the more popular solution. It is stupid but o well, Windows.

Prove to yourself it is downloading

If you cannot take it any longer and need to verify the downloads are downloading, you can go to C:\Windows\SoftwareDistribution and look in the Download folder. It should be increasing in size as files are added.

A more advanced way that is better proof:

1. Open Task Manager
2. Select Performance
   1. You should see a higher than normal level of Disk Access
   2. 
3. Select at the bottom “Open Resource Monitor”
   1. Open the Disk Section. Sorted by File.
   2. You should be able to find the SoftwareDistribution folder being accessed.
   3. 

Sources

1. Reddit Source 1 – Wait it out – Solution by Original Poster in his comment.
2. Reddit Source 2 – Turn off metered connections