Thanks for your answer Cedron! Nevertheless I need your converse assumption, i.e. $N \geq M$, and I believe it's because you should be using the combination of Frobenius' and Sylvester’s rank inequalities as a lower bound for the rank of the product of three matrices and the naive inequality with its dimension as an upper bound, which gives that the rank of the matrix of interest is $M \leq \text{rank}(C^* R_x^{-1} C) \leq N$. This is not very informative but I didn't come up with tighter inequalities. Let's see if someone can spot the problem:

By definition of PD, $x^* R_x^{-1} x > 0\quad \forall x \in \mathbb{R}^M \setminus \{0\}$ and since $C$ is full rank $\dim (\mathcal{R}(C)) = \min(M,N)= M$, and the projection $\tilde{x} := C y \neq 0\quad \forall y \in \mathbb{R}^N \setminus \{0\}$. Hence
\begin{align}
\tilde{x} = 0 \Longleftrightarrow y = 0 \tag{1}
\end{align}
Now we can see that $\tilde{x}^* R_x^{-1} \tilde{x} > 0\quad \forall \tilde{x} \neq 0$ following from PD of $R_x^{-1}$ so using the latter and (1),
\begin{align}
\tilde{x}^* R_x^{-1} \tilde{x} := y^* C^* R_x^{-1} C y > 0\quad \forall y \in \mathbb{R}^N \setminus \{0\} \tag{2}
\end{align}
and thus $C^* R_x^{-1} C$ is PD and hence invertible.