If the distances are a metric that would mean if A is close to B, C, D and E, then B, C, D and E should be close to each other. . Unless someone constructed the data to make it hard, the solution ought to be one data point and four of the data points closest to it.
For every point, create a list of all the other points, sorted by distance in ascending order. For each list calculate the sum of distances between the first point and the four nearest; the smallest sum would be your benchmark. Sort the points by this sum in ascending order. You now have everything arranged in an order that would tend to give you small sums of distances.
Now you can do an exhaustive search with shortcuts: You iterate through the first points with the smallest sum first, the second points in order of distance to the first points, etc. Most important that you ignore anything that cannot be optimal. Say your smallest sum of distances so far is 40, and you picked four points with a sum of distances of 26.9, then the fifth point cannot be further than 13.1 away from the first point. If the distances obey the triangular equation then you can take further shortcuts.
Say you have three points with a sum of distances of 7, the second and third points are at distance 2 and 3 from the first point, and the fourth point is at a distance d from the first point (and therefore the fifth at a distance at least d), then the last two points are at least d, d-2, and d-4 away from the first three points, so the sum of distances is at least 7 + 2 (3d - 6) = 6d - 5. So if the sum to beat is 40, we must have 6d - 5 ≤ 40 or d ≤ 7.5. That should seriously restrict the choice of the fourth point.
I'm sure it's possible to construct examples where this doesn't work well, but if you take say the locations of the largest 1000 cities in the world and you want the five closest to each other this would work quite well.
About proof that it gives the correct answer: Well, obviously yes. It does in principle an exhaustive search, except that it orders items in a way that small sums tend to be examined at the start of the search, and we can prune off search branches when it can be proven that they cannot lead to an optimal result. Sorting first means we get good (not optimal) results quickly which make the pruning more effective.
The counter example isn't a counter example. Yes, we will start with sorted lists that start with a point A on the inner n-gon, a few of the neighbouring points on the same n-gon, and some on the outer n-gon which isn't optimal. But that's just the starting point of the search. There was the assumption k << n, which is violated (k = n/2), so it will be harder to prune the search tree effectively. But that's because we don't have k << n.
