For a single qubit and a quantum operation, the fidelity $$ F_{|\psi\rangle\!\langle \psi|} = \mathrm{Tr}\bigg(U | \psi \rangle\!\langle \psi | U^\dagger \mathcal M\big(| \psi \rangle\!\langle \psi |\big)\bigg), $$
averaged over all possible initial states $|\psi\rangle$ (i.e., over the Bloch sphere) can be calculated by the fidelity averaged over the six states $|\pm\rangle,|\pm\rangle_x,|\pm \rangle_y$ (see this paper).
Is there a similar result for two qubits or more?
You can, as long as the states form a complex-projective 2-design.
To see it, start from expanding the given expression and observing that it is linear in $\mathbb{P}_\psi\otimes\mathbb{P}_\psi$, where $\mathbb{P}_\psi\equiv|\psi\rangle\!\langle \psi|$. More explicitly, this means that it can be reframed as an expression of the form $$F_{\psi}= \langle A, \mathbb{P}_\psi\otimes\mathbb{P}_\psi\rangle \equiv \operatorname{tr}(A^\dagger(\mathbb{P}_\psi\otimes\mathbb{P}_\psi)),$$ for some operator $A$ that you can find explicitly expanding all terms in your definition.
Therefore when averaging the fidelity over all states, you are effectively averaging over $\mathbb{P}_\psi\otimes\mathbb{P}_\psi$ over all (uniformly random) states $\psi$. A complex-projective 2-design is defined as a finite set of vectors such that averaging this quantity over these vectors equals the average over all states, hence the result. See e.g. https://en.wikipedia.org/wiki/Quantum_t-design for more info.
