Let $F$ be a countable dense subset of $E'$. By Hahn-Banach theorem, we need to find a countable subset $D$ of $E$ such that $$\forall f \in E' \big [ f \restriction \operatorname{span}_\mathbb R D \equiv 0 \implies f \equiv 0 \big ].$$
Clearly, $\operatorname{span}_\mathbb R D$ is a vector subspace of $E$. If $D$ satisfies above condition, then $\overline{\operatorname{span}_\mathbb R D} = E$. Clearly, $\overline{\operatorname{span}_\mathbb Q D} = \operatorname{span}_\mathbb R D$ and thus $\overline{\operatorname{span}_\mathbb Q D} = E$. Moreover, $\overline{\operatorname{span}_\mathbb Q D}$ is also countable.
Let's characterize $D$. Fix $f\in E'$ such that $f \restriction \operatorname{span}_\mathbb R D \equiv 0$. There is a sequence $(f_n)$ in $F$ such that $f_n \to f$. We have
$$
\sup_{x \text{ s.t. } |x|=1} \langle f_n-f, x \rangle = \|f_n-f\| \to 0.
$$
The hypothesis $f \restriction \operatorname{span}_\mathbb R D \equiv 0$ implies $f \restriction D \equiv 0$. It follows that
$$
\sup_{x \in D \text{ s.t. } |x|=1} \langle f_n, x \rangle \to 0.
$$
It suffices that $f_n \to 0$ or equivalently $\|f_n\| \to 0$. This suggests us a "bound"
$$
\|f_n\| \le\sup_{x \in D \text{ s.t. } |x|=1} \langle f_n, x \rangle.
$$
This "bound" maybe too strong to be true, but a weaker bound (by a positive constant $\alpha <1$) is enough for our goal, i.e.,
$$
\alpha\|f_n\| \le\sup_{x \in D \text{ s.t. } |x|=1} \langle f_n, x \rangle.
$$
For this inequality to hold, it suffices that for each $n$, there is $x_n \in D$ such that $|x_n|=1$ and
$$
\alpha\|f_n\| \le \langle f_n, x_n \rangle.
$$
Such pick of $x_n$ is possible due to $\alpha \in (0, 1)$. This completes the proof.
By Kakutani's theorem, $M$ is reflexive if and only if $B_M := \{x\in M | |x| \le 1\}$ is compact in the weak topology $\sigma(M, M')$. Notice that $\sigma(M, M')$ coincides with the subspace topology that $\sigma(E, E')$ induces on $M$. So $M$ is reflexive if and only if $B_M$ is compact in $\sigma(E, E')$.
Also by Kakutani's theorem, we have $B_E$ is compact in $\sigma(E,E')$. A closed subset of a compact set is also compact, so it suffices to show that $B_M$ is closed in $B_E$ w.r.t. $\sigma(E, E')$. This is indeed true because $B_M = M \cap B_E$ where $M$ is convex and closed in norm topology, and thus closed in $\sigma(E, E')$.
Best Answer
There is a sequence $(h_n)$ in $M^{\perp}$ such that $\|h_n -f\| \searrow \alpha$. It follows that $(h_n)$ is bounded by some $\beta \in \mathbb R_{>0}$. Let $B := (h_n)$. Then $B$ is a subset of the closed ball $\beta B_{E'}$ which is compact in weak$^\star$ topology $\sigma(E',E)$ by Banach–Alaoglu theorem. Then the weak$^\star$ closure $\overline{B}^\star$ is also compact in $\sigma(E',E)$. Also, the map $h \mapsto \|h-f\|$ is lower semi-continuous in $\sigma(E',E)$. Hence there is $g \in \overline{B}^\star$ such that $$ \|g-f\| = \inf_{h\in \overline{B}^\star} \|h-f\|. $$
It remains to show that $\overline{B}^\star \subseteq M^{\perp}$. It suffices to show that $M^{\perp}$ is closed in $\sigma(E',E)$. Let $(h_d)$ be a net in $M^{\perp}$ such that $h_d \overset{\ast}{\rightharpoonup} h\in E'$. This implies $0=\langle h_d, x \rangle \to \langle h, x \rangle$ for all $x\in M$. So $\langle h, x \rangle=0$ for all $x\in M$ and thus $h\in M^{\perp}$. This completes the proof.