Update: The answer is yes -- if $\mathsf{CH}$ is true then $\phi$ and $\phi^{-1}$ are conjugate in the group of self-homeomorphisms of $\omega^*$.
I've written this up in a new paper, which you can find on the arXiv: (link)
For the sake of anyone who's interested in how the proof goes (but not that interested), let me try to summarize some of what goes into it here.
Ultimately, the proof relies on a transfinite back-and-forth argument. This recursive argument needs to deal with $\mathfrak c$ tasks in succession, but the hypotheses of the recursion do not survive more than $\omega_1$ stages. Thus the argument can only succeed if $\mathfrak c = \omega_1$, i.e., if $\mathsf{CH}$ holds. (This is the only point in the entire proof where $\mathsf{CH}$ is needed.)
The limit steps of the recursion are trivial, and all the difficulty lies in the successor steps.
At successor steps, we wish to take a conjugacy between countable substructures of $\langle \mathcal P(\omega) / \mathrm{fin},\phi \rangle$ and $\langle \mathcal P(\omega) / \mathrm{fin},\phi^{-1} \rangle$ and extend it to a conjugacy between strictly larger substructures.
Furthermore, we must have at least some control over the growth of these substructures as the recursion progresses, so that we can ensure they cover $\mathcal P(\omega) / \mathrm{fin}$ in $\omega_1$ steps.
The standard approach to dealing with this kind of thing is known to model theorists as ``$\aleph_1$-saturation".
Roughly, if the structures $\langle \mathcal P(\omega) / \mathrm{fin},\phi \rangle$ and $\langle \mathcal P(\omega) / \mathrm{fin},\phi^{-1} \rangle$ were $\aleph_1$-saturated, then a conjugacy between two of their countable substructures could always be extended in the way we want.
Unfortunately, these structures are not $\aleph_1$-saturated (this is proved in Section 5 of the paper).
Our recursion asks us to perform $\omega_1$ tasks of a certain kind, but this lack of saturation means that some tasks of this kind are undoable.
So we cannot just launch into our recursion and deal with any instance of this task as it arises. Instead, we do the recursion in a particular way, carefully avoiding ever running into these undoable tasks.
The idea for avoiding these undoable tasks uses the model-theoretic idea of elementarity: if one of our two countable substructures is an elementary substructure, then the kind of extension described above can always be done.
Showing that this elementarity idea actually works is the hardest part of the proof, and it's really the heart of the whole thing. I won't say much about this piece of the argument here, except that it has less to do with set theory or model theory: it's just really tricky combinatorics, a careful analysis of the finite directed graphs that each capture some finite amount of information about $\langle \mathcal P(\omega) / \mathrm{fin},\phi \rangle$ and $\langle \mathcal P(\omega) / \mathrm{fin},\phi^{-1} \rangle$.
Let me mention that the final section of the paper includes two other related results, corollaries to the main theorem.
The first is that $\langle \mathcal P(\omega) / \mathrm{fin},\phi \rangle$ and $\langle \mathcal P(\omega) / \mathrm{fin},\phi^{-1} \rangle$ are elementarily equivalent. Unlike the main theorem, this corollary does not assume $\mathsf{CH}$.
The second states that $\mathsf{CH}$ implies there is an automorphism $\psi$ of $\mathcal P(\omega) / \mathrm{fin}$ that conjugates $\phi$ with itself in a nontrivial way: i.e., $\psi \circ \phi = \phi \circ \psi$, but $\psi \neq \phi^n$ for any $n \in \mathbb Z$.
$$$$
Original post:
This is a great question -- and it's wide open. Here's what I know about it:
$\bullet$ As you mentioned, it is consistent that $\phi$ and $\phi^{-1}$ are not conjugate. This observation was first made by van Douwen, soon after the publication of Shelah's result that you mention in your question. You mentioned forcing axioms, so let me point out that the non-conjugacy of $\phi$ and $\phi^{-1}$ follows from $\mathsf{MA}+\mathsf{OCA}$, which is a weak form of $\mathsf{PFA}$. This is due to Boban Velickovic.
$\bullet$ If it is consistent with $\mathsf{ZFC}$ that $\phi$ and $\phi^{-1}$ are conjugate, then it is consistent with $\mathsf{ZFC}+\mathsf{CH}$. (Proof sketch: If $\phi$ and $\phi^{-1}$ are conjugate in some model, then force with countable conditions to collapse the continuum to $\aleph_1$ and make $\mathsf{CH}$ true. Because this forcing is countably closed, it won't change much about the Boolean algebra $\mathcal P(\omega)/\mathrm{fin}$, and will preserve the fact that $\phi$ and $\phi^{-1}$ are conjugate.)
$\bullet$ Even better, the existence of certain large cardinals implies that if it is possible to force "$\phi$ and $\phi^{-1}$ are conjugate" then this statement is already true in every forcing extension satisfying $\mathsf{CH}$. This follows from a theorem of Woodin concerning what are called $\Sigma^2_1$ statements about the real line (explained further here). The assertion "$\phi$ and $\phi^{-1}$ are conjugate" is an example of such a statement. (Very roughly, this theorem seems to suggest that if this statement is consistent, then it should follow from $\mathsf{CH}$. At any rate, trying to prove it from $\mathsf{CH}$ seems like a reasonable strategy.)
$\bullet$ In fact, Paul Larson has pointed out to me that the statement "$\phi$ and $\phi^{-1}$ are conjugate" is a now very rare example of a $\Sigma^2_1$ statement about the real line whose status we do not know under $\mathsf{ZFC}+\mathsf{CH}$ (plus large cardinal axioms).
$\bullet$ I proved a partial result a few years ago, showing that $\mathsf{CH}$ implies $\phi$ and $\phi^{-1}$ are semi-conjugate:
$\qquad$Theorem: Assuming $\mathsf{CH}$, there is a continuous surjection $Q: \omega^* \rightarrow \omega^*$ such that $$Q \circ \phi = \phi^{-1} \circ Q.$$
The paper is "Abstract $\omega$-limit sets," Journal of Symbolic Logic 83 (2018), pp. 477-495, available here. In the same paper, I show that the forcing axiom $\mathsf{MA}+\mathsf{OCA}$ implies $\phi$ and $\phi^{-1}$ are not semi-conjugate. (Or rather, I show that this is a corollary to a deep structure theorem of Ilijas Farah.)
$\bullet$ Finally, in a more recent paper (to appear in Topology and its Applications, currently available here), I show that there is no Borel set separating the conjugacy class of $\phi$ and the conjugacy class of $\phi^{-1}$ (in the space of self-homeomorphisms of $\omega^*$ endowed with the compact-open topology). Roughly, this shows that if $\phi$ and $\phi^{-1}$ fail to be conjugate, it's not "for any real reason" -- or at least not for any nicely definable topological reason.
