Convex polygon formulation
Theorem 1. For every polygon with edge length sequence $a_1,\ldots,a_m$, there exist a convex polygon with same edge length sequence.

Proof. Here.

Definition. $a_1,\ldots,a_n$ be $n$ non-negative reals. It satisfies (strict) $n$-gon inequality if $2a_j &lt; \sum_{i=1}^n a_i$ for all $j$.
Theorem 2. The sequence $a_1,\ldots,a_n$ is a sequence of edge length for a polygon iff it satisfies $n$-gon inequality.

Proof. Here. (note the proof here requires advanced math and also proves Theorem 1)
The problem reduce to:

Given a sequence of $n$ non-negative reals, find a $k$ element subsequence that satisfies $k$-gon inequality.

An simple algorithm: Check if $a_i,\ldots,a_{i+k-1}$ is a solution for every $1 \leq i\leq n-k+1$. If none of them work, then there is no solution.
Proof. If we have any solution $a_{i_1},\ldots,a_{i_k}$, find the largest $j$, such that $a_{i_{j+1}}-a_{i_j}&gt;1$, (i.e. there is a gap). If there is no such gap then we are done. If there is one, then $a_{i_2},\ldots,a_{i_{j}},a_{i_{j+1}-1},a_{i_{j+1}},\ldots,a_{i_k}$ is also a solution. (intuitively, we used the largest element in the gap and removed the smallest element). We can repeat this step (at most $k-1$ times) and fill in all the gaps. Eventually we produced a solution of the form $a_{i_k}-k+1,a_{i_k}-k,\ldots,a_{i_k}-1,a_{i_k}$ for some $i$.
The algorithm can be done naively in $O(kn)$ time. Maybe there is a smarter way to do it.
A interesting follow up question:

Given a sequence of $n$ non-negative reals, find the longest subsequence $S$, such that every $k$ element subsequence of $S$ satisfies $k$-gon inequality.