This seems a little tricky since you seem (ab)use native Category for things that aren’t quite the same (Villa and Housekeeper). You will probably need to write a custom logic since WP won’t just “get” the bit that if you are on one specific category (Villa) you want to query for another (Housekeeper).
As for querying itself WP by now has support for very elaborate taxonomy queries.
Loosely the part of query for it would something like this:
'tax_query' => array(
'relation' => 'AND',
array(
'taxonomy' => 'category',
'field' => 'slug',
'terms' => 'housekeeper',
),
array(
'taxonomy' => 'region',
'field' => 'slug',
'terms' => 'mykonos',
),
),