Let $\{A_k\}_{k=1\dots N}$ and $\{B_k\}_{k=1\dots N}$ be two sets of $d\times d$ matrices over the complex numbers such that for any length $L$ and any sets of indices $\{j_1,j_2,\dots j_L=1\dots N\}$ the following trace equality holds:
$\text{Tr}(A_{j_1}A_{j_2}\dots A_{j_L})=\text{Tr}(B_{j_1}B_{j_2}\dots B_{j_L})$
This equality is obviously satisfied if there exists an invertible matrix $S$ such that $B_k=SA_kS^{-1}$ for all $k=1\dots N$.
Under what conditions can we guarantee that there is such an $S$ intertwiner?
With the help of some tips from @Omnomnomnom I found the answer. It is written in "Shirshov's theorem and representations of semigroups" by A. Freedman, R.N. Gupta, R.M. Guralnick. Their Corollary 2.7 on page 163 deals with this problem.
The answer is: If the matrix algebras generated by the two sets are semisimple, then there is a desired common similarity transformation. The semisimple property was the one I was looking for.
Perhaps a simpler explanation is given in "On the Unitary Similarity of Matrix Families" by Yu. A. Al'pinKh. D. Ikramov. Theorem 1 is what I needed. Here the condition is the complete reducibility, which is equivalent to the semisimple property.