If you restrict to pure states, all orthogonal multipartite states are locally distinguishable. By "local" I mean here a LOCC measurement where you measure the different parties in sequence and the each measure can to be conditioned to the previous measurement results — it's thus a relatively simple kind of LOCC measurement that doesn't require any back and forth.
This was originally shown in Walgate et al. 2000.
To show this, let $|\Psi\rangle,|\Phi\rangle\in \mathbb{C}^n\otimes\mathbb{C}^m$ be arbitrary pure bipartite orthogonal states, $\langle\Psi|\Phi\rangle=0$.
For locally distinguishability it is enough to find an ON basis $\{|u_a\rangle\}\subset\mathbb{C}^n$ such that $\langle\Psi|(\mathbb{P}_{u_a}\otimes I)|\Phi\rangle=0$ for all $a$, using the notation $\mathbb{P}_{u_a}\equiv|u_a\rangle\!\langle u_a|$. Indeed, this would imply that, performing this projective measurement, regardless of which outcome $a$ is found, the resulting conditional states on $\mathbb{C}^m$ remain orthogonal, and therefore deterministically distinguishable.
First attempt at a proof — We want to show that there is always such a basis. To this end, observe that
$$\langle \Psi|(\mathbb{P}_{u_a}\otimes I)|\Phi\rangle
= \langle u_a|\underbrace{\operatorname{tr}_2(|\Phi\rangle\!\langle\Psi|)}_{\equiv \Phi\Psi^\dagger}|u_a\rangle = \langle u_a|M|u_a\rangle,$$
where $2M= \Phi\Psi^\dagger+\Psi\Phi^\dagger$, and I used the fact that $\Phi\Psi^\dagger-\Psi\Phi^\dagger$ is skew-Hermitian and thus has vanishing expectation values.
Note that I'm denoting with $\Psi$ the matrix whose elements are those of the vector $|\Psi\rangle$, that is, $(\Psi)_{ij}=\langle i,j|\Psi\rangle$.
The matrix $M$ is Hermitian and thus admits an eigendecomposition of the form $M=\sum_k\lambda_k \mathbb{P}_k$.
If you then define $|u_a\rangle\equiv \frac{1}{\sqrt n}\sum_b \omega^{ab} |b\rangle$, with $\omega\equiv e^{2\pi i/n}$, you get
$$\langle u_a|M|u_a\rangle = \frac1n\sum_{bc} \omega^{-ab+ac} \langle b|M|c\rangle
= \frac1d \sum_b \lambda_b =\frac1n \operatorname{tr}(M)=0.$$
We thus conclude that the orthonormal basis $\{|u_a\rangle\}\subset\mathbb{C}^n$ satisfies the constraints, i.e. performing a projective measurement on it preserves orthogonality on the conditional states on $\mathbb{C}^m$, and thus one can always deterministically distinguish any pair of orthogonal pure states via local measurements.
Note that I'm showing that the basis to use is the Fourier transform of the eigenbasis of $M$. Though I think you don't need to use this specific basis: any other orthonormal basis that is unbiased wrt the eigenbasis of $M$ should work just the same — it just so happens that the QFT is a good standard way to get an unbiased basis.
IMPORTANT EDIT: I'm leaving the above paragraph for reference, but I later found out that this proof is wrong. It only works as presented in some cases, such as when $\Psi\Phi^\dagger$ is normal, or when it's 2x2. The issue is that it uses $\langle u_a|B|u_a\rangle=0$ for skew-Hermitian $B$, which is simply wrong in general. Nevertheless, the statement still holds: one can prove in general that any traceless matrix has zero diagonal in some basis, as discussed in this math.SE post. It seems the proof isn't constructive in the general case though (and note that Walgate et al's proof also requires some enlarging of the space shenanigans for the general case).
Toy example 1
Consider the bipartite example with
$$\sqrt2|\Psi\rangle = |00\rangle+|11\rangle,
\qquad
\sqrt2|\Phi\rangle = |00\rangle-|11\rangle.$$
Note that measuring in the computational basis wouldn't work: if you for example measured $|0\rangle$ on the first qubit, the second qubit would be $|0\rangle$ regardless of which of the two states you're given.
To find the right measurement basis, we can follow the procedure outlined above: compute
$$\Psi\Phi^\dagger = \frac12\begin{pmatrix}1&0\\0&-1\end{pmatrix}.$$
In this case this is Hermitian so we don't need to introduce the $M$ operator. Clearly the eigenbasis of this is the computational basis, and therefore the correct basis to measure in is $|\pm\rangle$, that is, the eigenbasis of the Pauli X matrix.
You can verify that this works because measuring $|+\rangle$ on the first qubit the second qubit would transform as
$|\Psi\rangle \to |+\rangle$, $|\Phi\rangle \to |-\rangle,$
while if you get $|-\rangle$ on the first qubit you have
$|\Psi\rangle \to |-\rangle$, $|\Phi\rangle \to |+\rangle$.
You therefore clearly always have orthogonal states on the second qubit regardless of the first measurement result. Furthermore, you don't even need to change the computational basis in this case: you just measure both qubits in the $|\pm\rangle$ basis.
It's however worth noting that the resulting protocol still involves some classical communication, because to figure out which bipartite state you've been given from the second measurement result, you need to know the first measurement result.
Namely, you'll overall (correctly) guess the input was $|\Psi\rangle$ if you measure (+,+) or (-,-), and you'll guess $|\Phi\rangle$ if you measure (+,-) or (-,+).
Toy example 2
Say now
$$\sqrt2|\Psi\rangle = |00\rangle+|11\rangle,
\qquad
\sqrt2|\Phi\rangle = |01\rangle-|10\rangle.$$
This gives $\Psi\Phi^\dagger=\frac12\begin{pmatrix}0&-1\\1&0\end{pmatrix}$, which is interesting because it's not Hermitian, and if you were to define the $M$ operator you'd just get $M=0$. This tells you that it doesn't matter what measurement basis you use for the first qubit, because the leftover second qubit will remain orthogonal no matter what. You can also see this as direct consequence of $\Psi\Phi^\dagger$ being skew-Hermitian, and thus its diagonal is always made of zeros.
Toy example 3
Let's ease into the multipartite case. Say we want to distinguish between two GHZ-like states:
$$\sqrt2|\Psi\rangle = |000\rangle+|111\rangle,
\qquad
\sqrt2|\Phi\rangle = |000\rangle-|111\rangle.$$
In such cases we start showing how to measure the first qubit leaving the rest orthogonal. In other words, we first treat the states as bipartite in a $\mathbb{C}^2\otimes\mathbb{C}^4$ space. Note how this means that $\Psi,\Phi$ are not square matrices anymore: we have
$$\Psi= \frac{1}{\sqrt2}\begin{pmatrix}1&0&0&0\\0&0&0&1\end{pmatrix},
\qquad
\Phi= \frac{1}{\sqrt2}\begin{pmatrix}1&0&0&0\\0&0&0&-1\end{pmatrix},\\
\Psi\Phi^\dagger = \begin{pmatrix}1&0\\0&-1\end{pmatrix}.$$
Following the usual recipe we conclude that the first qubit needs to be measured in the $|\pm\rangle$ basis. The leftover two-qubit states will be the Bell states $|00\rangle\pm|11\rangle$, and thus we already know how to continue the procedure from the first example.
