UPDATED. I've changed the verification strategy and computationally proved the statement for all $k\leq 30$, using the following randomized algorithm.
Randomized algorithm. For a given list of $k$ values of $x$'s sorted in increasing order, we set initially $s=0$, and at each of $k$ steps we identify the range of list elements that belong to the interval $[-s,1-s)$, select one of them, say $v$, randomly, remove it from the list, and add $v$ to $s$ (thus keeping $s$ in the interval $[0,1)$). The algorithm succeeds if we are able to make all $k$ steps, and fails otherwise (when at some step there are no suitable elements in the list).
From Fedor's observation it follows that for a fixed $k$, we can restrict our attention to values $x_1 = \frac{m}{2^k-1}$ for $m\equiv 2\pmod4$ in the interval $[2,2^k-2]$ and the sequences of $x_i$ emerging from them. For each such sequence (sorted in increasing order), we run the randomized algorithm multiple times until it succeeds.
It's worth to note that for a fixed $k$, the average number of algorithm runs (over all $m$) used in my computation was about $k/2$.