New
#1
Never use it myself but just tried it, same result as you. Even disabling Web search didn't help. Quite frankly it's garbage.
You could install "Classic Shell" and voila! http://www.classicshell.net/
I have just found out why the search wasn't working on my pc!
Last week I installed a new Samsung SSD and loaded the Samsung magician software.
It was this software that had turned off the indexing on my drive, so I've changed the settings.
I might even uninstall the Samsung Magician software.
Everything is working now (I hope).
@ Cornishman
By your screenshot, it looks like Cortana's not totally set up, you should have 4 icons in the menu:
right click on Start and choose Search, you may get some more options to complete the setup.