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). Giordano–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) \mathrel E g(y).$$

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

Edited to add: the book "Cantor minimal systems" by Ian Putnam is a good reference for information and bibliographical data about this area. Clemens's paper can be found here: Generating equivalence relations by homeomorphisms.