Why do I get “No testimonials found” when using category and tags

Because, there’s no testimonials having that category with those tags.

When using tags only, it’s possible to select from many testimonials unless you check the “Require all tags” option. Then only testimonials with all of those tags are selected.