So I was looking through related questions on this site and the book "Proper and Improper Forcing" by Shelah kept popping up. So I checked it out and the appendix actually resolves the question. I rephrase the proof there because I think this way it's simpler and also because it suggests an interesting question (see the end).
Let $P_0 := \mathsf{Fn}(\omega_2, 2, \omega)$ and let $P_1 := \mathsf{Fn}(\omega_3, 2, \omega_1)$. The following lemma is basic:
Lemma
$P_0 \Vdash MA^*$.
Proof.
Let $G$ be $P_0$-generic over $\mathbb{V}$. Let $f: \omega_1 \to 2$ be the generic function.
Suppose $X \subseteq \omega_1$ codes an $\omega_1$-sequence of open dense sets $(\mathcal{O}_\alpha: \alpha < \omega_1)$ of $(\,^\omega \omega)^{\mathbb{V}[G]}$. Then for some $I \subset \omega_2$ with $|I| = \aleph_1$, we have $X \in \mathbb{V}[G \cap \mathsf{Fn}(I, 2, \omega)]$. But let $\alpha = (\sup I) + 1$ and let $x \in \,^\omega \omega$ be defined by $x(n) = f(\alpha + n)$. Then $x \in \bigcap_{\alpha < \omega_1} \mathcal{O}_\alpha$.
End proof of lemma.
We aim to show that $P_0 \times P_1 \Vdash MA^* \land \Phi^*$ provided we start with a model of $CH$. This proof is gleaned from the proof of Theorem 2.11 in the Appendix of Shelah's "Proper and Improper forcing."
Customarily we view this iterated forcing as starting with $P_1$ and following it by $P_0$, since $(P_0)^{\mathbb{V}^{P_1}} = P_0$. However to get $\Phi^*$ we have to view it the other way around. So we need to look at $P_1$ in $\mathbb{V}^{P_0}$.
Lemma.
Suppose $G_0$ is $P_0$-generic over $\mathbb{V} \models CH$. Then in $\mathbb{V}[G_0]$:
(a) $\mathsf{Fn}(\omega_3, 2, \omega) \subset P_1 \subset \mathsf{Fn}(\omega_3, 2, \omega_1)$, and for any two elements $p, q \in P_1$, if $p$ and $q$ are compatible then $p \cup q \in P_1$,
(b) $P_1$ has the $\omega_2$ c.c.,
(c) Forcing with $P_1$ does not add any reals,
(d) The set $\mathcal{B} := \{\mbox{dom}(p): p \in P_1\}$ is closed under intersections, unions, and relative complements, and if $p \in P_1$ and $X \in \mathcal{B}$, then there is some $q \, || \, p$ with $\mbox{dom}(q) = X$,
(e) If $X \subseteq \omega_3$ is countable there is some (countable) $Y \in \mathcal{B}$ containing $X$.
Proof.
(a) Obvious.
(b) Showing that $(Q \mbox{ has the $\omega_2$ c.c.})^{\mathbb{V}[G_0]}$ is the same as showing it in $\mathbb{V}$ (just go through the proof of the $\Delta$-system lemma and see that it works for any antichain in $Q$).
(c) Let $G_1$ be $Q$-generic over $\mathbb{V}[G_0]$. Then also $G_1$ is $Q$-generic over $\mathbb{V}$, and $G_0$ is $P$-generic over $\mathbb{V}[G_1]$ and $G_0 \times G_1$ is $P \times Q$-generic over $\mathbb{V}$.
Now it suffices to show that if $x \in \mathcal{P}(\omega) \cap \mathbb{V}[G_0 \times G_1]$ then $x \in \mathcal{P}(\omega) \cap \mathbb{V}[G_0]$. To see this, consider a $P$-nice name $\sigma$ for $x$ in $\mathbb{V}[G_1]$; so $\sigma = \{(\hat{n}, A_n): n \in \omega\}$ where $A_n \in \mathbb{V}[G_1]$ is an antichain in $P$. So $A_n \subseteq P$ is countable, so $A_n \in \mathbb{V}$ already (since $(Q \mbox{ is $\omega$-closed})^{\mathbb{V}}$). Hence $\sigma \in V$ so $x \in \mathbb{V}[G_0]$.
(d) Obvious.
(e) The existence of $Y$ follows from the c.c.c. of $P_0$.
End proof of lemma.
Lemma.
Suppose $2^{\aleph_0} \leq \aleph_2$ and $Q$ is a forcing notion satisfying $(a)$ through $(e)$ above. Then $Q \Vdash \Phi^*$.
Proof.
Suppose towards a contradiction that $1_Q \Vdash \lnot \Phi^*$. Then (by the maximal principle) there are names $\dot{F}, \dot{S}$ such that
\begin{eqnarray*}
1_Q &\Vdash& ``\mbox{ $\dot{F}: \,^{<\omega_1} 2 \to 2$ and $\dot{S} \subseteq \omega_1$ is stationary and } \\
&& \forall g: \omega_1 \to 2 \,\,\, \exists f: \omega_1 \to 2 \mbox{ such that } \{\alpha \in \dot{S}: \dot{F}(f \restriction_\alpha)= g(\alpha)\} \\
&& \mbox{ is nonstationary}."
\end{eqnarray*}
We can choose $\dot{F}$ and $\dot{S}$ to be nice names; that is $\dot{F} = \{(\hat{(\eta, i)}, A_{\eta, i}): \eta \in \,^{<\omega_1} 2, i \in 2\}$ and $\dot{S} = \{(\hat{\alpha}, A_\alpha) : \alpha < \omega_1\}$, where each $A_{\eta, i}$ and each $A_\alpha$ is an antichain in $Q$. (This uses that $(\,^{<\omega_1} 2)^{\mathbb{V}} = (\,^{<\omega_1} 2)^{\mathbb{V}^Q}$.
Let $\mathcal{A} = \bigcup_{\eta, i} A_{\eta, i} \cup \bigcup_{\alpha} A_\alpha$; so by the $\omega_2$-c.c., $|\mathcal{A}| \leq \aleph_2$. Hence $D:= \bigcup_{A \in \mathcal{A}} \mbox{dom}(A)$ has cardinality at most $\aleph_2$. Hence after relabeling we can suppose that $D \cap \omega_1 = \emptyset$.
Let $\dot{c}$ be the nice $Q$-name for the generic $\omega_3$-sequence: $\dot{c} = \{(\hat{(\alpha, i)}, \{(\alpha, i)\}): \alpha < \omega_3, i \in 2\}$. Let $\dot{g} = \dot{c} \restriction_{\omega_1}$, i.e. $\dot{g} = \{(\hat{(\alpha, i)}, \{(\alpha, i)\}): \alpha < \omega_3, i \in 2\}$.
Then $1_Q \Vdash ``\exists f: \omega_1 \to 2$ such that $\{\alpha \in \dot{S}: \dot{F}(f \restriction_\alpha) = g(\alpha)\}$ is nonstationary." So for some nice $Q$-name $\dot{f} = \{(\hat{(\alpha, i)}, B_{\alpha, i}): \alpha < \omega_1, i \in 2\}$, we have $1_Q \Vdash ``\dot{f}: \omega_1 \to 2$ and $\{\alpha \in \dot{S}: \dot{F}(\dot{f} \restriction_\alpha) = \dot{g}(\alpha)\}$ is nonstationary." Let $\dot{C}$ be a nice name for a club subset of $\omega_1$ such that $1_Q \Vdash ``\forall \alpha \in \dot{S} \cap \dot{C}: \dot{F}(\dot{f} \restriction_\alpha) \not= \dot{g}(\alpha)$. Say $\dot{C} = \{(\hat{\alpha}, B_\alpha): \alpha < \omega_1\}$.
Let $G$ be $Q$-generic over $\mathbb{V}$; we work in $\mathbb{V}[G]$. Let $F = \dot{F}_G$, let $S = \dot{S}_G$, let $g = \dot{g}_G$, let $f = \dot{f}_G$ and let $C = \dot{C}_G$. For each $\alpha < \omega_1$, let $p_\alpha$ be the unique element of $G \cap (B_{\alpha, 0} \cup B_{\alpha, 1})$ and let $q_\alpha$ be the unique element of $G \cap B_\alpha$ if it exists, or $q_\alpha = 1_Q$ if $G \cap B_\alpha = \emptyset$. Let $D_\alpha = \mbox{dom}(p_\alpha) \cup \mbox{dom}(q_\alpha)$ and let $X_\alpha = \bigcup_{\beta < \alpha} D_\beta$. Then the set $C^* = \{\alpha < \omega_1: X_\alpha \cap \omega_1 \subseteq \alpha\}$ is club. So there is some $\delta \in S \cap \mbox{acc}(C) \cap C^*$.
(In the following we use the properties $(a), (d)$ and $(e)$ heavily.)
Let $I \subset \omega_3$ be countable such that $I \supseteq \delta \cup \{X_\alpha \backslash \omega_1\}$ and $I \in \mathcal{B}$ (where $\mathcal{B}$ is as in the lemma). Let $J = I \backslash \{\delta\}$ (possibly $I = J$); so $J \in \mathcal{B}$.
Let $p_0$ be the unique element of $G \cap A_\delta$, so $p_0 \Vdash \delta \in \dot{S}$. Let $p_1 = g \restriction_J$, so $p_1 \Vdash \dot{f} \restriction_\delta = f \restriction_\delta$ and $p_1 \Vdash \dot{C} \cap \delta = C \cap \delta$. Since $\delta \in \mbox{acc}(C)$, $p_1 \Vdash \delta \in \dot{C}$.
Let $p = p_0 \cup p_1$; note that $\delta \not \in \mbox{dom}(p)$.
Back in $\mathbb{V}$, $p \Vdash ``\hat{\delta} \in \dot{S} \cap \dot{C} \land \dot{F}(\dot{f} \restriction_\delta) = i"$, for some $i \in 2$. But let $q = p \cup \{(\delta, i)\}$; then $q \vDash \dot{F}(\dot{f} \restriction_\delta) = \dot{g}(\delta)$, contrary to definition of $\dot{C}$.
End proof of lemma.
Theorem.
Suppose $\mathbb{V} \models CH$. Then $P_0 \times P_1 \Vdash MA^* \land \Phi^*$.
Proof.
Let $G_0 \times G_1$ be $P_0 \times P_1$-generic over $\mathbb{V}$. By Lemma 1, $\mathbb{V}[G_0 \times G_1] = \mathbb{V}[G_1][G_0] \models MA^*$. By Lemma 2, $\mathbb{V}[G_0 \times G_1] = \mathbb{V}[G_0][G_1] \models \Phi^*$.
End proof of theorem.
Question. Under what conditions can we find a $Q$ satisfying conditions (a) through (e)?
