Locally compact subspace is an intersection of an open and closed set

Without assuming that $X$ is Hausdorff (and using the definition of local compactness given) the result is not true.

Let $X$ be any set with at least two elements, and consider the trivial (anti-discrete) topology on $X$. Clearly this space has the property that the nonempty open sets with compact closures form a base (indeed, there is only one nonempty open set, and it's closure is clearly compact), and so this space is locally compact. Note, too, that any nonempty proper $M \subseteq X$ is also locally compact (another anti-discrete space), but will not be the intersection of an open and a closed subset of $X$.

However, the result does follow if we assume that $X$ is Hausdorff. (Then local compactness is equivalent to every point having an open neighbourhood with compact closure.)

To wit: given $x \in M$, let $V_x$ be a neighbourhood of $x$ in $M$ such that $\mathrm{cl}_M ( V_x ) = \overline{V_x} \cap M$ is compact. Now $\overline{V_x} \cap M$ is also a compact subset of $X$, so by Hausdorffness $\overline{V_x} \cap M$ is closed (in $X$). Fix an open $W_x \subseteq X$ such that $W_x \cap M = V_x$. Clearly we have that $$\overline{ W_x \cap M } \cap M = \mathrm{cl}_M (V_x).$$ Note, now, that as $W_x \cap M \subseteq \overline{ W_x \cap M } \cap M$, we have that $$ W_x \cap \overline{M} \subseteq \overline{ W_x \cap \overline{M} } = \overline{ W_x \cap M } \subseteq \overline{ W_x \cap M } \cap M \subseteq M, $$ (and clearly $x \in W_x \cap \overline{M}$).

Setting $U = \bigcup_{x \in M} W_x$, it follows that $U$ is open in $X$, and $M = U \cap \overline{M}$, as desired.

Let us assume that $X$ is a KC space, that is a space where all compact sets are closed (In particular, each Hausdorff space is KC). Then $M$, as a subspace, is also KC. Now it suffices if every point in $M$ has a compact neighborhood, as then we can assume that this compact neighborhood is the closure of some open neighborhood. With these hypotheses, let's show that $M$ is the intersection of an open and a closed subset of $X$:
Each $x\in M$ has an open neighborhood $N$ in $M$, whose closure relative to $M$ is compact and a subset of $M$. But that implies, as $X$ is KC, that this relative closure is closed in $X$, hence $$\overline N^M=\overline N\subseteq M$$ Since $N$ was open in $M$, there is an open $N'$ such that $N=M\cap N'$. Now $$\overline M∩N'=\overline{M∩N'}^{N'}=\overline N^{N'}=\overline N∩N'\subseteq M∩N'=N$$ This means that $N=\overline M∩N'$ is also a neighborhood of $x$ in $\overline M$. Since $x\in M$ was arbitrary, and $N\subseteq M$, this shows that $M$ is open in $\overline M$. In particular, $M$ is the intersection of some open set with $\overline M$.

Edit (06/12/2015): The proof becomes shorter using the notion of local closedness and assuming that you have proven that a locally closed subset is open in its own closure. Here a set $Y$ of a space is locally closed if each $y\in Y$ has a neighborhood $U$ such that $Y\cap U$ is closed in $U$.
Now if $Y$ is a locally compact subspace of the KC space $X$, then each $y\in Y$ has a neighborhood $K'$ in $X$ such that the relative neighborhood $K=Y\cap K'$ is compact. But that means that $Y\cap K'$ is closed, so $Y$ is locally closed.

The obvious choice of closed set here is $\overline M$; it is the smallest closed set containing $M$. With this choice of closed set, it suffices to choose an open set which excludes $\overline M - M$.

I claim each point $m\in M$ has an open neighborhood $U_m$ which excludes $\overline M - M$. For $m \in \text{int}(M)$, this is not hard to see. For $m \in M\cap \partial M$, choose a compact neighborhood $K_m\subseteq M$. Considering $K_m$ as a subspace of $\overline M$, we have that $\text{int}_{\overline M}(K_m)$ is open in $\overline M$, so there is an open set $U_m$ so that $U_m \cap \overline M = K_m\subseteq M$. Hence $U_m\cap (\overline M - M)$ is empty, as desired.