Should I use custom taxonomy or custom post type

So, at the end of the day, your content is about resorts (that is, “destination” = resort?

If so:

Custom Post Type: destination (semantically, it would be “resort”, but you can use “destination” to meet your client’s needs)
Custom Taxonomy(ies): location (country, city, etc.)

EDIT:

How to parse the terminology:

Post: noun
Taxonomies: adjectives

The Post is the thing – the content. Any taxonomies are ways of describing your Posts.