I'll post an answer based on the comments above.

Since $t$ is self-adjoint, we can write $t= t_+-t_-$ where $t_+$ and $t_-$ are positive elements with $t_+ t_- = 0$. The latter condition ensures that $\|t\| = \max\{\|t_+\|, \|t_-\|\}$.

Assume, without loss of generality, that $\|t\| = \|t_+\|$.

Let $\epsilon > 0$. By definition of the operator norm, there is an element $z$ in the unit ball of $E$ such that $\|t_+^{1/2}\| \le \epsilon + \|t_+^{1/2}z\|.$

Consider the isometric unital $*$-morphism
$$C(\sigma(t)) \to C^*(1,t): f \mapsto f(t)$$

given by continuous functional calculus. Define $f \in C(\sigma(t))$ to be $f=0$ on $\sigma(t)\cap [-\infty,0]$ and to be $1$ on $\sigma(t)\cap [\delta,\infty]$ and $\operatorname{Im}f\subseteq [0,1]$, where $\delta>0$ is chosen such that $2s^{1/2}< \epsilon$ when $0 \le s \le\delta$, and consider the element $f(t)\in C^*(1,t)\subseteq \mathcal{L}_A(E)$. Then we define $x:= f(t)z \in E$, and we note that
$\|x\| \le \|f(t)\|\|z\| \le \|f\|_\infty =1.$ By definition of $t_-$, we see that $t_-f(t) = 0$. Hence,
$$\|\langle tx,x\rangle\| = \|\langle t_+ x,x\rangle\| = \|t_+^{1/2}x\|^2.$$

Let $g(s) = \max\{s,0\}$. Then $$\|g^{1/2}f-g^{1/2}\|_\infty = \sup_{s \in [0,\delta]} |s^{1/2}f(s)-s^{1/2}| \le \sup_{s \in [0,\delta]} 2s^{1/2}\le \epsilon.$$

It follows that

$$\|t_+^{1/2}x-t_+^{1/2}z\|=\|t_+^{1/2}f(t)z-t_+^{1/2}z\| \le \epsilon.$$

Hence, $$\|t_+^{1/2}\| \le 2\epsilon + \|t_+^{1/2}x\|=2\epsilon + \|\langle tx,x\rangle\|^{1/2} \le 2 \epsilon + M^{1/2}.$$

Letting $\epsilon \to 0$, we obtain $\|t_+^{1/2}\| \le M^{1/2}$. Squaring both sides and invoking the $C^*$-identity, we obtain
$$\|t\| = \|t_+\| \le M$$
and the other inequality is proven.