Let $G$ be given by the group presentation $G = \langle a,b \mid S \rangle$, where $S = \{aa,bbb\}$. The formal definition of $G$ is:
Let $F$ be the free group on $\{a,b\}$. Let $H$ be the conjugate closure of $S$, i.e. $H$ is the subgroup of $F$ generated by $\{fsf^{-1} : f \in F, s \in S\}$. Then we can define the quotient group $G = F/H$.
Let $x,y \in F$ be words consisting of only letters $a, b$. Using the formal definition of $G$ above, how can we show that if $x=y$ in $G$ (i.e. $xH = yH$), then there is a finite sequence of operations changing $x$ to $y$ where in each operation we either add/remove an $aa$ or add/remove a $bbb$ to $x$?
Thoughts: We can write $y^{-1}x = \text{reduce}(f_1 s_1 f_1^{-1} f_2 s_2 f_2^{-1} \dots f_k s_k f_k^{-1})$, where $f_i \in F$, and $s_j \in S' = \{aa,bbb,a^{-1}a^{-1},b^{-1}b^{-1}b^{-1}\}$. Here reduce($w$) is the reduction of $w$ in the free group by cancellation of consecutive $a,a^{-1}$ or $b,b^{-1}$. But I'm not sure how to proceed from here.
Edit: Can we also show this holds for arbitrary $S$? For example, $S = \{aa,bbb,ababab\}$?
You might not find this answer satisfactory, because it involves more general abstract concepts.
But (I think) what you are asking is equivalent to asking whether the monoid defined by the given presentation embeds into the group defined by the same presentation.
The answer to this is yes in your example, and also in the example in your edit (and in any example in which there is exists $k>0$ with $x^k \in S$ for all generators $x$), because in these examples the generators, and hence all elements in the monoid defined by the presentation, manifestly have 2-sided inverses, and so this monoid is itself a group.
In this situation, the monoid/group $M$ defined by the presentation is naturally isomorphic to the group $G$ defined by the same presentation. To see this, let $X$ be the set of generators of $M$. Then an element of $G$ consists of equivalence classes of words over $X \cup X^{-1}$, but by assumption, each $x^{-1}$ is equal in $G$ to a word $\bar{x}$ over $X$, and so the same applies to any word over $X \cup X^{-1}$. We need to show that two words over $X$ are equivalent in the monoid $M$ if and only if they are equivalent in the group $G$. Clearly equivalence in $M$ implies equivalence in $G$. For the converse, if two such words $v,w$ are equivalent in $G$, then we can transform $v$ to $w$ by inserting or deleting defining relators of $M$ or strings $xx^{-1}$ or $x^{-1}x$ for $x \in X$. To move from $v$ to $w$ in $M$, whenever we insert $xx^{-1}$ of $x^{-1}x$, we instead insert or delete $x\bar{x}$ or $\bar{x}x$, both of which are relators of $M$ by assumption.
But the answer to your general question is no, and the simplest example is $\langle a,b \mid ab \rangle$. In the group defined by this presentation the word $ba$ defines the identity element, but that is not true in the monoid, so the word $ba$ cannot be reduced to the empty word by inserting and removing strings $ab$.
Note that the elements of this monoid have normal form $\{ b^ia^j : i,j \ge 0 \}$.