I think the best solution realistically is just to make a large number of minimum-size regions that are all safe spawn spots. If you are concerned about spawns being 'knowable' beforehand just make a fuckload of possible spawns all over the arena. It will be tedious to create/name them and put their center locations into a bigass location array on map init, but once you've done so you can just randomize an integer, use that int as an index for the array, and then check that location against all other 'picked' spawn locations to see if any are too close. If so, randomize that most recent spawn again until it's far enough away. It's possible that this method results in the Mth through Nth out of N spawns always being too close to others, so you could build a failsafe into the process to start over if that happens, or just accept the suboptimal spawn.
A variant of this is to abuse what a region actually is. Turns out what GUI calls regions are actually JASS rects (in this reply from here onward I will be using the true JASS definitions to describe the two objects, to avoid confusion). The difference is that rects are rectangular boxes that can't be rotated and regions are abstract collections of rects. It's possible to get "random point in rect" but not possible to get "random point in region"; you can, however, check if a given point/xy-coordinate is within a particular region. Cover the arena in one big rect, then also make a bunch of smaller rects that cover all areas of the map that should be un-spawnable. On map init, add all the un-spawnable rects into one big region; when you need a safe point, randomize points in the big region until you find one that isn't in the un-spawnable region. Check distance to other chosen spawn points same as above (with the same caveat about closeness).
(It's possible this could be done 'in reverse' by subtracting all the bad rects from the main big rect using RegionClearRect instead of RegionAddRect, but I don't know for sure that will work properly.)
As long as there aren't any enclosed areas where a unit would have enough room to move around in but never leave, you can test randomized locations for pathability by placing an item on the location you randomized. The item will automatically be moved to the next closest pathable spot the game can find for it. Randomize point, place item, update point to the item's new location, then compare against all prior chosen points (same caveats).
To avoid the caveats about closeness you could instead divide the arena radially (or some geographic blob-like method) into 9 zones, and then either use the item method to test randomized points in each zone or use the regions-made-up-of-rects approach to determine safe locations. More work but potentially better results.
