Segment "more than one country"

You can't create a segment with an embedded calculated metric, such as Approximate Count Distinct.

You could set up a cohort table with Countries on both the X and Y-axis and a metric like unique visitors. Unfortunately, this will only show visitors who saw both countries and will be incredibly clunky because there are so many countries.

Another option would be to create a visitor segment in which you require a visitor to have both a specific Countries value and not that specific Countries value (see screenshot). If you apply this segment to the unique visitors metric you will get the number of unique visitors that were associated with both the United States and another country. You can also create a calculated metric using this segment. Unfortunately, you'll need to pick a country to start.

since yesterday, there is a new segment options exactly what you need: "distinct count"

see here: https://marketing.adobe.com/resources/help/en_US/analytics/segment/seg_operators.html

basically create a segment (visit) with condition "distict count countries > 1"

What's bizarre is that I don't have access to Visitors in the segment building. I've contacted Adobe support to figure this out. I'm an admin and have access to each and every metric.

BernardoC​ "unique visitors" is not a segmentable metric. Instead, you should choose the "Visitor" container and then build out your criteria for what types of visitors you are looking for within that container.