Caution: Self answer ahead!
Let's understand it with an example of a binary $AB$ compound.
A correlation function for a particular type of cluster (pair, triangle, tetrahedron, etc.), $\rho$, is defined as
\begin{equation}
\rho_\alpha\: =\: <cluster function>_\alpha,\tag{1}
\end{equation}
Where $\alpha$ represents the type of cluster and $<...>$ represents an average over all clusters equivalent to $\alpha$ by symmetry.
\begin{equation}
cluster function = \prod_i{\gamma_{\alpha_i,M_i}}_{(\sigma_i)} \tag{2}
\end{equation}
The cluster function is a product of a quantity which in the sense of binary alloys is called a spin variable (inspired by the Ising model), whereas, in general, for multicomponent systems seems to have no name. The paper cited in the question denotes it as $\gamma_{\alpha_i,M_i}$, where $i$ represents a lattice point, $\alpha_i$ takes two values, 0 for when $i$ is not in a certain cluster and 1 when it is, and $M_i$ is simply the number of type of atoms, 2 for binary, 3 for ternary, and so on. Note: $\alpha$ and $\alpha_i$ aren't the same.
Convention: $\gamma$ equals 1 for any site $i$ that isn't part of the particular cluster $\alpha$ ($\alpha_i\: =\: 0$).
$\sigma_i$ in equation 2 is an occupation variable which holds the information about which atom occupies lattice site $i$. It takes values from $0$ to $M_i - 1$. For example, in a ternary alloy, $\sigma_i\: =\: 0, 1,$ or $2$.
\begin{equation}
\sigma_i\: =\:
\begin{cases}
-1, & \text{atom A on i}\\
+1, & \text{atom B on i}
\end{cases}
\tag{3}
\end{equation}
Let's calculate the pair correlation for $AB$:
$\alpha\: =\: 2$ (pair)
$M_i\: =\: 2$ (binary)
In a perfectly random phase, each lattice point $i$ is equally likely to be occupied by $A$ and $B$ since it is an equiatomic alloy.
$\alpha_i$ will be $0$ for all lattice points that aren't in the particular pair we are calculating the cluster function for and $1$ for those that are part of the pair. So the four possible values of ${\gamma_{\alpha_i,M_i}}_{(\sigma_i)}$ for a binary are:
${\gamma_{0,2}}_{(0)}\: =\: 1$
${\gamma_{0,2}}_{(1)}\: =\: 1$
${\gamma_{1,2}}_{(0)}\: =\: -1$
${\gamma_{1,2}}_{(1)}\: =\: +1$
In a random phase of $AB$, every lattice site $i$ on average has a $0.5$ occupation of $A$ and $0.5$ of $B$. To calculate the correlation function, $\rho_\alpha$, we need to take an average of cluster functions for all equivalent clusters $\alpha$. Every pair (even higher clusters) in a perfectly random phase is equivalent, so all cluster functions are the same and equal to the average, hence equal to the correlation function.
The value of ${\gamma_{1,2}}_{(\sigma_i = 0,1)}\: =\: 0.5\cdot (-1) + 0.5\cdot (+1) = 0$ for each site $i$.
So the cluster function for a pair which contains two lattice points $=\: 0\cdot 0\: = 0$.
Finally, the correlation function, $\rho_2$, is equal to $0$.