I think the problem will be getting the list of messages out of Mail—this will almost certainly require AppleScript, as Mail doesn't allow you to copy a selection of messages.
And while I'm not enough of an AppleScript expert to say for sure, but it looks to me like the search results aren't available to AppleScript in any way, so you might have to have the macro build a new Smart Folder for each search, then get the contents of that smart folder.
What are the reasons for needing the list in Keyboard Maestro and not just directly in Mail? You could have KKM send the search to Mail, then activate Mail, and you'd be looking at a list of messages where you can click one top open that email.
Spotlight offers essentially the same capability. A search in Spotlight using this exact format—specifically, no spaces on either side of the colon—should be comparable once the Show All In Finder option is selected at the bottom of the initial list of results.
Here's one I use to search for messages from the sender of the selected message using a similar approach. It works fine without the pause between activating the search field and inserting the text.
Ah ... I really wish they'd left that site online :(. I inquired about hosting it myself without advertising, but never heard back. (Not as a live site, but as a data source.)
You'll need to make sure a viewer window, not a message, is frontmost in Mail for ⌥⌘F to work. If it is frontmost then you can swap the second pause for a "pause until menu item 'Paste' is enabled", which will make the second phase more robust and maybe faster.
Are you looking to search through "several mailboxes" at the same time, or sequentially? Do you want to open the found emails all at once or one at a time?
As @griffman says, you might be able to do this with AppleScript -- it could depend on the complexity of the search, and speed will depend on the number of emails you are searching through as there's no metadata index to take advantage of. But it could be as simple as:
tell application "Mail"
open (every message of mailbox "INBOX" of account id "5A8C12FC-3487-44AF-B5B0-F82B29740552" whose sender contains "Gek")
end tell
...if you are searching the "From" field (the account ID is particular to my setup, if this method seems worth trying we can go further with it).