League and Divisions problem (np-hard)
Balanced k-means clustering would probably work reasonably well here.  Unfortunately the true cost structure can't be modelled with this (or any clustering algorithm that I know of); you would need to instead use some increasing function of the distance from the cluster centroid (this could be just the distance itself, or e.g. a small positive power).  Balanced k-means will then try to cluster the teams into divisions in such a way that the sum of these per-team costs is minimised, while enforcing a hard upper bound (your max) on the number of teams in a division.  The chosen number k of divisions, as well as these upper bounds, implies a lower bound on the division size, though this won't necessarily agree with your desired min.  Hopefully, playing with the parameters a bit could get you close.

The idea is basically the same as regular k-means clustering, except that in the assignment phase, instead of assigning each point (team) to its nearest cluster (division), you solve an instance of the Assignment Problem in which each team is represented as a worker and each division is represented as max job slots: this enforces that each division receives at most max teams.  The problem can be solved with e.g. the Hungarian algorithm.

There's a paper here, but it seems to be behind a paywall unfortunately: https://link.springer.com/chapter/10.1007/978-3-662-44415-3_4