To elaborate on Anadim's answer, if $C$ is a code of length $n$, then any codeword in $C$ is uniquely determined by any $k$ of its positions if and only if $C$ has minimum distance at least $n-k+1$. The Singleton bound says that, over an alphabet of size $q$, a code of length $n$ and minimum distance $n-k+1$ has size at most $q^k$. So if $k = o(n)$ then there are no asymptotically good codes satisfying your requirements.
If $q$ is large then the Singleton bound is attained by any MDS (maximum distance separable) code, for example, by the Reed–Solomon codes mentioned by Anadim. So if you have $q^m$ possible strings then, using Reed–Solomon codes, the feasible pairs are $(n,k)$ for $n$ and $k$ such that $q \ge n \ge k \ge m$. The restriction $q \ge n$ means this is not an asymptotic result, but for practical purposes, if you can take $q$ large, you can then make $k$ small compared to $n$.
Over the binary alphabet, the only MDS-codes of length $n$ are the repetition code of size $2$, the parity check code of size $2^{n-1}$, and the complete code consisting of all $2^n$ words of length $n$. In this case Hamming's packing bound is stronger than the Singleton bound, and the Plotkin bounds are stronger still when the minimum distance is large compared to $n$. In particular, one of the Plotkin bounds states that if $k < n/2$ then a binary code of length $n$ and minimum distance $n-k+1$ has size at most $2(n-k+1)$. This shows that if $k=o(n)$ then any binary code satisfying your requirements is necessarily very small.
If you are willing to take $k\approx n/2$ then it might work well to use a shortened Hadamard code of length $2k-1$, size $2k$ and minimum distance $k$. These attain one of the Plotkin bounds, so are the largest possible binary codes of length $2k-1$ that allow any codeword to be reconstructed from any $k$ of its positions. (A special case when $k=4$ is the subcode of the binary Hamming code of length $7$ consisting of all words of even weight.)
