カテゴリー、タグを組み合わせて検索できる機能がほしい

検索機能の拡張は、それぞれの状況によってやりたいことや出したい情報が違ったりするので、汎用的な機能としてテーマやプラグインで提供するのが（僕には）難しいです。既存のプラグインで対応されるか、独自に開発されるのが良いかと思います。

独自に実装する場合は、適当なクエリを get で渡して、それを pre_get_posts フックで受け取って tax_query に追加する、というのが基本的なやり方だと思います。そんなに難しくないと思うので、ググりながら実装されてみると良いかもです。