Sample Complexity for Order Statistics
One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ samples (after transforming to Z). 

It can be shown that $Z_{(t)}\sim \text{Beta}(t,m+1-t)$. Using this, $Z_{(m\cdot k/n)}=F(X_{(m\cdot k/n)})$ is a consistent estimator for $F(\mu_{k:n})$.

As to the rates, since the exact distribution of $Z_{(t)}$ is known, it can be shown that ${E}[|F(X_{(m\cdot k/n)})-F(\mu_{k:n})|]\approx \sqrt{\frac{2}{\pi}}\sqrt{\frac{\min\{k/n,1-k/n\}}{m}}$. Now if you have some kind of constraint on $F$, say $F$ is Lipschitz with constant $c$, ${E}[|X_{(m\cdot k/n)}-\mu_{k:n}|]\le \frac{1}{c}\cdot {E}[|F(X_{(m\cdot k/n)})-F(\mu_{k:n})|]\approx \frac{1}{c}\sqrt{\frac{2}{\pi}}\sqrt{\frac{\min\{k/n,1-k/n\}}{m}}$. Therefore $X_{(m\cdot k/n)}$ is a reasonable estimator for $\mu_{k:n}$.

On the other hand, if there is no constraint on $F$ whatsoever, there is no way one can estimate $\mu_{k:n}$ consistently even with $m\rightarrow \infty$.