Reconstruct a matrix from its traces

Unfortunately even the generic situation is bad. Since we know the eigenvalues, we should search for the orthonormal system of eigenvectors $v_i$ of $A$. We have ($e_i$ is the standard basis) $$ Tr(A^k\Gamma)=\sum_i\left[\sum_j\gamma_j \langle v_i,e_j\rangle^2\right]\lambda_i^k $$ so, in effect, you have the knowledge of $\sum_j\gamma_j \langle v_i,e_j\rangle^2$ ($i=1,2,3$). However, these three values are not independent: since the matrix $(\langle v_i,e_j\rangle^2)_{ij}$ is bistochastic, their sum is just $Tr \Gamma$, so you have only $2$ independent equations, while the orthogonal matrices form a 3D manifold. Thus in the generic case you should expect a continuous 1-parametric family of solutions.

I do not think you can reconstruct $A$ just from this information.

Take $\Gamma=I_n$, let $M$ be any orthogonal $n \times n$ matrix and set $B={}^tMA M$.

Then $A$ and $B$ are two similar (symmetric) matrices, and so all their positive powers $A^k$ and $B^k$ have the same eigenvalues (and in particular the same trace).