Decomposing the n-cube into vertex-disjoint paths
I found the following result due to Gregor and Dvorak. They show that if the sets $S$ and $T$ are balanced (in the sense that they contain the same amount of vertices from both bi-partitions of the $n$-cube), then such paths exists whenever $2k-e &lt; n$, where $e$ is the number of pairs $(s_i, t_i)$ that form edges in $\mathcal{Q}_n$. The paper can be found here: http://www.sciencedirect.com/science/article/pii/S0020019008002238

I can construct an example when $k = 2$, $e=0$ and $n=3$, so this result isn't completely tight, however.