This answer does not give a full answer to the question. I started working out what I could; so, I'll post it in case it is of use to anyone.
Let $[n] = \{1,2,\dots, n\}$ and $[n'] = \{1',2', \dots, n'\}$. We will use the convention that $i'' = i$. A diagram $D$ is a perfect matching of the the complete graph on the vertex set $[n] \cup [n']$. We will think of any $D$ as $(S_D,T_D,f_D,M_D,M'_D)$. Here $S_D \subseteq [n]$, $T_D \subseteq [n']$, and $f:S_D \to T_D$ is a bijection while $M_D$ and $M'_D$ are perfect matchings on $[n] \setminus S_D$ and $[n'] \setminus T_D$ respectively. So, $D$ is the prefect matching $\{\{i,f_D(i)\} : i \in S_A\} \cup M_A \cup M'_A$ which partitions $D$ is edges which "cross" and edges which live entirely in $[n]$ or $[n']$.
Let us take two diagrams $A$ and $B$. We will assume that $M_A \subseteq M_B$. Otherwise there is no solution since $M_A \subseteq M_{AC}$ for any $C$. Here by abuse of notation we let $AC$ denote the both the product in the Brauer algebra and the diagram which is the product in the Brauer monoid. Now let us try to find $C$ such that $AC = x^m B$.
First, for all $\{i,j\} \in M_B \setminus M_A$ put $\{f_A(i)', f_A(j)'\}$ in $M_C$. This ensures that $\{i,j\} \in M_{AC}$.
Since $M_A \subseteq M_B$ we have $S_B \subseteq S_A$. For each $i \in S_B$ we set $f_C(f_A(i)') = f_B(i)$ while adding $f_A(i)'$ and $f_B(i)$ to $T_A$ and $T_C$ respectively. This will ensure that $f_{AC} = f_B$.
Now let $r = |M_A| = |M'_A|$ and $s = |M_B| = |M'_B|$. We have that $s \geq r$. Also, we must have $r \geq m$ to be able to obtain a solution. At this point in our construction of $C$ any unmatched vertices in $[n]$ will be glued to vertices in $M'_A$ when performing the Brauer product. Also all unmatched vertices in $[n']$ are matched in $M'_B$.
Choose $m$ edges from $M'_A$ and for each $\{i',j'\}$ chosen we put $\{i,j\}$ in $M_C$. This will give us the factor of $x^m$.
Next inject the remaining $r-m$ edges in $M'_A$ into $M'_B$. If $\{i',j'\}$ maps to $\{k',l'\}$ then set either $f_C(i) = k'$ and $f_C(j) = l'$ or else $f_C(i) = l'$ and $f_C(j) = k'$. Finally add the edges of $M'_B$ not covered by this injection directly into $M'_C$. This all results with $M'_B = M'_C$.
This construction gives $2^{r-m} \binom{r}{m} (s)_{r-m}$ solutions $C$ where $AC = x^mB$. Here $(s)_{r-m} = s(s-1) \cdots (s-r-m-1)$ is the falling factorial. In the case $r=m$ we get a single solution which should be the unique solution in that case. Though in general this doesn't cover all solutions.