Solution 1:

Stop the Windows Update Service (via services.msc or in a cmd.exe which is started as admin via net stop wuauserv - this improves speed of installing the MSU update which you have to download), download and install this update by double click on the MSU:

Installing and searching for updates is slow and high CPU usage occurs in Windows 8.1

If the hack to stop Wu service doesn't speedup install of the MSU, extract the MSU with 7-zip and use DISM to install the update.

dism /online /add-package /packagepath:C:\Windows8.1-KB3102812-x64.cab

This skips the check if the update is required and works around the hang at "Searching for updates on this computer" while installing a MSU.

Do a reboot and check again for new updates. Now Windows Update will work and show new updates in a few minutes.