Complex Taxonomy scheme

Set your system up like this:

• locations – CPT
• administrative – hierarchical taxonomy
• natural – hierarchical taxonomy
• type – non-hierarchical taxonomy

In the administrative taxonomy, you would create your tree: countries on the first level, regions second, departments and so on. Then, you would assign your locations to the smallest administrative denominations among your taxonomies – like the departments in your example. Next, in the taxonomy page you list all posts in that taxonomy and its children (that is actually the default).

The same approach goes for the natural taxonomy. Go as deep as you need and attach your posts to the “leafs” of your taxonomy tree.

As for the types of locations, you would not have separate taxonomy pages, but use them in the administrative and natural taxonomies to filter your view to that exact type of location: hotel, park and so on.

UPDATE:

Taxonomies are used for classification, and I don’t think linking the leaves from different taxonomy trees would be a good idea. AFAIK, WP does not allow that either.

But you have no obligation to limit yourself to only one CPT. The way I see your situation, you have your resorts CPT, but you should also add CPTs for the parks and tourist areas. This way, you would have 3 CPTs in total, all sharing 2 custom taxonomies: admin and natural.

After that, you’ll need to link some of these CPTs together. I can think of 3 possible solutions to do that:

1. Use their geographical position: add an ACF Google Map field for each post, save lat and lng in separate meta fields (ACF stores the address, lat and lng in a serialized field so you cannot query them), then use $wpdb->get_results to query the DB directly and get your CPTs by distance (see Distance between Latitude and Longitude Coordinates in SQL or MySQL calculate distance between two latitude/longitude coordinates).
2. Connect your posts using Posts 2 Posts: that used to work great, and, AFAIK, it still does today, but the author of the plugin stopped supporting it 2 years ago. From what I researched a couple of months before, there is no better alternative for linking posts, either free or paid.
3. A workaround simulating #2: use ACF Relationship fields + ACF Post-2-Post. This plugin only works with ACF v.5, so you need to use either the PRO version of ACF, or download the free variant of v.5.x from their site, as on the WP plugin repository they still have v.4.x.

Depending on your exact needs and capabilities, you could use any of the above methods, and possibly even combine #1 with #2 or #3.