I think you can use Search using the Charm bar (This is how Search is supposed to work in Win 8. You can also hook your Metro apps into it)

Go into the store
Hit Windows+C
Click Search

>How come this award winning user interface of Windows Store has no Search field? <g>
>
>>That is the Windows store
>>
>>>Do you remember (before you upgraded to Windows 8.1) if when you went to the Metro Store tile if you immediately saw the Microsoft Store? When I click on Store I see all kinds of apps on sale but no Windows Store.