The condition
\begin{equation}
\{x\in A: [a,x]=0\}=\{x\in A: [b,x]=0\}
\end{equation}
implies that $a$ and $b$ commute.
(Edit: after spelas noted that there was a relation in the example I wrote, now I'm rewriting the answer with an example where there is no relation)
This is of course no characterization, as
Jesse's example above shows. But I don't think much can be said in this generality: consider $A=L^\infty[0,1]\oplus \ell^\infty(\mathbb{N})$, $a=f\oplus 0_m$, $b=0_n\oplus g$, where $f,g$ are respectively the functions $f(t)=t$, $g(n)=1/n$. Then $\{a\}'\cap A=A$, $\{b\}'\cap A=A$. So for this $a,b$ we have the equality among the centralizers, but no "correspondence" (in the language of the original question) between the two elements; indeed, $W^*(b)=\mathbb{C}\,1\oplus\ell^\infty(\mathbb{N})$, $W^*(a)=L^\infty[0,1]\oplus\mathbb{C}\,1$.
There's nothing very particular about this example, any two selfadjoint elements in the centre of a C$^*$-algebra $A$ will do.