If $k = 2n - 1$, we can choose all points with $x$-coordinate, $y$-coordinate are $1$. Then, clearly there is no parallelogram. Thus, any $k \le 2n-1$ does not satisfy the condition.

Next, we will prove that $k = 2n$ satisfies. Indeed, let $x_1, x_2, ..., x_n$ be the number of points whose $x$-coordinate are $1, 2, ..., n$ respectively. Clearly
$$x_1 + x_2 + \dots + x_n = 2n.$$
Consider the segments formed by connecting $2$ points with the same $x$-coordinate. If there are $x$ points, then at least $x-1$ segments with different lengths will be generated (we take the point with the lowest ordinate and connect it to the remaining $x-1$ points). Thus, with $1 \le i \le n$, among the points with the same $x$-coordinate $i$, we can choose a set $S_i$ with size $x_i - 1$ consists of segments with different lengths. If in $S_1, S_2, ..., S_n$ there are two segments have the same length, it is easy to see that the four corresponding vertices will form a parallelogram, satisfying the problem.

Conversely, if there are no segments with the same length, then notice that
$$|S_1| + |S_2| + \dots + |S_n| = (x_1 - 1) + (x_2 - 1) + \dots + (x_n - 1) = n,$$
but the values in these sets are smaller than $n$, because their length is the difference between two $y$-coordinate, and these coordinates only belong to $\{1, 2, ..., n\}$.

Obviously this is a contradiction.

Therefore the minimum value to find is $k_{min} = 2n$.