For each pair of points, consider the family of lines parallel to the line that connects the points. Project all the points on the line perpendicular to the family, sort the coordinate, and find the smallest coordinate distance that covers k points.

Note that since at least one line on the border must contain two points, instead of sorting one can use partition and nth_element. That is the time complexity does not need logarithm: O(n^3).