As far as I understand, you can't search through extra fields.
Something came up, check this module:
labs.smartwebstudio.com/ , it does the job but it is a separated search module, just to search a single category, child categories, a chosen extra field etc, it even have other options like select box to filter by a determined item into a drop down extra field, which will avoid tags for filtering results.
You can use various instances of the module in same page to search and select by different criteria.
It outputs the filtered result through generic.php, which is a drawback since you can only override once, and affect the output of tags and author at the same time. I'm waiting for an answer from the developer to see if is possible to get the results assigned to a custom template override, and avoid changing the generic.php.
Another thing to notice, is that to get it to work, you may have to do a few slight changes to the K2 core files, the author provides the needed override, as well as the backup to restore the original core files.
Hope it helps.