Right-clicking in the search box should give you a menu with the choice of "Paste" or "Undo."
It would appear as if the update suggested to me by "neilpzz" in the post before yours has partially solved the problem of the context menu.
This optional update took nearly 30 minutes to download and install, but the ALT+SPACE window menu still appears on right-click of the Search Bar when some other element of the Explorer window has input focus, or when I right-click on the Explorer Search Bar when an entirely different application (Word, Firefox, Thunderbird, etc) has foreground focus.
If Explorer is the foreground application, and the Search Box is currently focused and has the keyboard input cursor, then a Mouse Right-Click or keyboard PROPERTIES key press brings up the appropriate context menu.
At least actual searching from within Explorer is working properly again, including advanced filters and boolean operators.