Enumerate all pairs, in order of increasing distance, efficiently
Consider all the point on the x-axis, then you are describing sorting $X-X$. A special case of $X+Y$ sorting(one can actually show they are equivalent in terms of running time). This is not known to be sortable in less than $O(n^2 log n)$ time. Interestingly $O(n^2)$ comparisons suffice.