I am new in compressive sensing and I would like to know if there already exists a deterministic or probabilistic approach to estimate the locations of the $k$ non-zero entries in the $k$-sparse vectore $x$.
Actually some greedy algorithms like MP, exactly do that. They iteratively find signal supports (location of non-zero elements) using measurements and measurement matrix, and reconstruct original signal. However, in case you are asking for a method to find signal supports from measurements all at once, I think there is no such thing (may be someone discover it someday!). If there was a such a thing, the computational cost of the CS recovery algorithms wouldn't be so high.
Fore further information on greedy recovery algorithms, take a look at these: