This is a tentative answer based on @ValterMoretti's comment and the GNS theorem following these notes. If anything is found to be wrong because I misunderstood it, please let me know.
Let $\mathcal{A}$ be the $C^\ast$-algebra and $\phi : \mathcal{A}\to\mathbb{C}$ a state. Endow the algebra it with the semi-inner product $\langle x,y\rangle = \phi(x^\ast y)$.
Consider then $N_\phi = \{x\in \mathcal{A} : \langle x,x\rangle = 0\}$. The GNS construction is based on noting that $N_\phi$ is a closed left ideal so that on the quotient $\mathcal{A}/N_\phi$ one gets a well-defined inner product descending from $\langle \cdot,\cdot\rangle$. More precisely let $\Pi : \mathcal{A}\to \mathcal{A}/N_\phi$ be the canonical surjective projection, namely $\Pi(x)=x+N_\phi$. Define then
$$\langle \Pi(x),\Pi(y)\rangle=\langle x,y\rangle$$
It turns out that $\langle \Pi(x),\Pi(x)\rangle= 0$ if and only if $\Pi(x) = 0$. Indeed by definition the condition is equivalent to $\langle x,x\rangle = 0$ so that $x\in N_\phi$ and thus $\Pi(x) = 0$ as wanted.
Define $\mathcal{H}_\phi$ the completion of the inner product space $\mathcal{A}/N_\phi$ so that it is a Hilbert space. We represent $\mathcal{A}$ in $\mathcal{H}_\phi$ by
$$\pi_\phi : \mathcal{A}\to \mathcal{A}(\mathcal{H}_\phi)$$
given the action on the elements of $\mathcal{A}/N_\phi$ by $\pi_\phi(a)(x+N_\phi)=ax+N_\phi$.
Remember now that the elements of $\mathcal{H}_\phi$ are to be the usual state vectors. They are thus the elements of $\mathcal{A}/N_\phi$ plus the limits of Cauchy sequences.
Let then $a\in \mathcal{A}$, so that we want to define its matrix elements.
Let $\Phi,\Psi\in\mathcal{A}/N_\phi$ be two state vectors so that $\Phi=\Pi(x)$ and $\Psi=\Pi(y)$. We then have
$$\langle \Phi,\pi_{\phi}(a)\Psi\rangle=\langle \Pi(x),\pi_{\phi}(a)\Pi(y)\rangle=\langle \Pi(x),\Pi(ay)\rangle=\phi(x^\ast ay).$$
Thus we see that the matrix elements as done in QM are obtained in the above form from elements of $\mathcal{A}$ which descend to states.
I believe that to generalize the whole of $\mathcal{H}_\phi$ one will finaly just need to argue with the limits of Cauchy sequences.