I realize this post is a few years old, but I just wanted to extend this to anyone still struggling through this issue.
The company I work for still uses VS2015 so in turn I still use VS2015. I recently started working on a RPC application using C++ and found the need to download the Win32 Templates. Like many others I was having this "SDK 8.1 was not found" issue. i took the following corrective actions with no luck.
None of the attempts above corrected the issue for me...
I then found this article on social MSDN https://social.msdn.microsoft.com/Forums/office/en-US/5287c51b-46d0-4a79-baad-ddde36af4885/visual-studio-cant-find-windows-81-sdk-when-trying-to-build-vs2015?forum=visualstudiogeneral
Finally what resolved the issue for me was:
I hope this saves anyone else from almost 3 full days of frustration and loss of productivity.