Start menu search is unfortunate broken in Windows 11 (even more so than in W10). It needs to do a Web search before returning results, which makes it too slow to be reliably useful in my opinion.

It's easily solved by installing Power Toys and using the search feature from there instead (activated with alt + space, like in Linux & Mac)