Here is a general upper/lower bound on the Wasserstein distance between $\mu$ and $\nu$ based on a maximal coupling with respect to their total variation distance: $$
(1/2) \min_{x_i \ne x_j} c(x_i, x_j) \sum_{k=1}^n |1/n - \nu_k| \le \mathcal{W}(\mu,\nu) \le (1/2) \max_{x_i \ne x_j} c(x_i, x_j) \sum_{k=1}^n |1/n - \nu_k| \;.
$$ More generally, the upper bound realized by a maximal coupling takes the form: $$
\mathcal{W}(\mu,\nu) \le \frac{\sum_{i \ne j} c(x_i, x_j) (\mu_j-\nu_j)^+ (\nu_i-\mu_i)^+}{\sum_k (\mu_k-\nu_k)^+}.
$$ For completeness, the maximal coupling itself is explicitly given by: draw the first component $X$ from $\mu$ and then set the second component equal to:
$$
Y=\begin{cases} X & \text{with probability $\frac{\nu(X)}{\mu(X)} \wedge 1$} \;, \\
\tilde{Y} & \text{otherwise} \;.\end{cases}
$$ where $\tilde{Y}$ is a random variable (independent of all the preceding ones)  drawn from the remaining probability suitably normalized $\tilde{\mu}(x) = \frac{\nu(x) - \nu(x) \wedge \mu(x)}{\sum_k (\mu_k-\nu_k)^+}$.