Even with a homeomorphism, preserving $=*$ does not imply reflection. There might be an easy example, I'm not sure; at any rate it follows from a result in topological dynamics (the "absorption lemma" of Giordano--Putnam--Skau) that such examples exist.

Let me elaborate a bit: by results of Giordano--Putnam--Skau, there exists a minimal homeomorphism of $X=\{0,1\}^{\mathbb N}$ which induces the relation that you denote $=^*$ (and which is often denoted $E_0$); there is an explicit construction (via a Bratteli diagram) in a paper of Clemens. By this, I mean that being in the same $\varphi$-orbit is the same as being $=^*$-equivalent.

Denote such a homeomorphism by $\varphi$, fix some point $x \in X$, and let $E$ be the relation obtained from $=^*$ by splitting the class of $x$ in its positive semi-orbit under $\varphi$, and its negative semiorbit. (So, all classes are the same as $=^*$, except that the class of $x$ has been split in two pieces).  Girodano--Putnam--Skau prove that there is a homeomorphism $g$ of $X$ such that for all $x,y \in X$ one has
$$x=^*y \Leftrightarrow g(x) E g(y) $$

Since $E$ is contained in $=^*$, yet not equal to it, such a $g$ preserves $=^*$ without reflecting it.