The basic reason is that a Lebesgue measurable function is one with the property that preimages of Borel sets are Lebesgue measurable. The main reason why we define things that way is because not all continuous functions are Lebesgue-Lebesgue measurable, so if we defined measurability through Lebesgue-Lebesgue measurability then the Lebesgue integral would not be an extension of the Riemann integral.
Anyway, the structural reason why this has anything to do with composition is because:
$$(f \circ g)^{-1}(A)=g^{-1}(f^{-1}(A)).$$
Thus if $A$ is Borel and $f,g$ are Lebesgue-Borel measurable, then $f^{-1}(A)$ might be Lebesgue measurable but not Borel measurable, and so $g^{-1}(f^{-1}(A))$ could fail to even be Lebesgue measurable. To do this construction, it suffices to take $g$ to be a Lebesgue-Borel measurable function which is not Lebesgue-Lebesgue measurable, find a set $M$ which is Lebesgue measurable such that $g^{-1}(M)$ is not Lebesgue measurable, and then set $f=1_M,A=\{ 1 \}$.
As you may be aware, making up Lebesgue nonmeasurable sets is never really "constructive", but there is still a way to build such a $g$ and show it has the necessary properties, provided we can conjure up a suitable Lebesgue nonmeasurable set in the course of the proof. To do that, we look at
$$h : [0,1] \to [0,2], h(x)=c(x)+x$$
where $c$ is the standard Cantor function. It is easy to see that $h$ is a strictly increasing continuous function. It's perhaps less easy to see that $\mu(h(C))=1$ where $C$ is the standard Cantor set; you might call this lemma 1. With that in hand, you can select a Lebesgue nonmeasurable set $N \subset h(C)$ (you might call this ability to construct a nonmeasurable subset of a positive measure set lemma 2).
Now $h^{-1}(N)$ is a Lebesgue measurable set (because it is a subset of $C$). But its preimage under $h^{-1}$ (i.e. $N$) isn't Lebesgue measurable. It turns out this is only possible because it is not Borel, because $h(B)$ is Borel for every Borel $B$ since $h$ is strictly increasing.
In the end we can take $g=h^{-1},M=h^{-1}(N)$ in the notation of the third paragraph.
I wrote this answer essentially by following along with https://www.math3ma.com/blog/lebesgue-but-not-borel but the answer is complete even if this link dies.
Attention: We are going to use the terminology used in the question, including $m_*$ to denote Lebesgue outer measure:
$E$ is Lebesgue measurable if $\forall \epsilon > 0$, there exists an open set $O$ such that $E \subset O$ and $m_*(O-E) < \epsilon$.
and
$E$ is Caratheodory measurable, if $m_*(A) = m_*(A \cap E) + m_*(A \cap E^c)$ for all $A \subseteq \Omega$.
Let us prove that if $E$ is Lebesgue measurable, then $E$ is Caratheodory measurable.
Suppose $E$ is is Lebesgue measurable. Given any $\epsilon >0$, let $O_\epsilon$ be an open set such that $E \subset O_\epsilon$ and $m_*(O_\epsilon-E) < \epsilon$.
Given any $A \subseteq \Omega$, we have, taking any any $\epsilon >0$
\begin{align*}
\mu_*(A) &\leqslant \mu_*(A \cap E) + \mu(A\cap E^c) \\
& \leqslant \mu_*(A \cap O_\epsilon ) + \mu_*((A\cap O_\epsilon ^c) \cup (A\cap O_\epsilon \cap E^c))\\
& \leqslant \mu_*(A \cap O_\epsilon ) + \mu_*(A\cap O_\epsilon ^c) +\mu_*(A\cap O_\epsilon \cap E^c)\\
& \leqslant \mu_*(A \cap O_\epsilon ) + \mu_*(A\cap O_\epsilon ^c) +\mu_*(O_\epsilon \cap E^c)\\
& \leqslant \mu_*(A) + \epsilon
\end{align*}
where in the last step we used the fact that open sets are Caratheodory measurable.
So we have proved that, for any $\epsilon >0$,
$$
\mu_*(A) \leqslant \mu_*(A \cap E) + \mu(A\cap E^c) \leqslant \mu_*(A) + \epsilon
$$
So
$$
\mu_*(A) = \mu_*(A \cap E) + \mu(A\cap E^c)
$$
So $E$ is Caratheodory measurable.
Best Answer
You seem to have provided a counterexample yourself.
If $A$ is any non-measurable subset of $\mathbb R$, then $A\times\{0\}$ is nevertheless Lebesgue measurable in $\mathbb R^2$ because it is null. Its intersection with the $x$-axis is $A$ itself, which is not measurable in $\mathbb R$.