Sorry, I don't have the reputation to comment.

1. Most of the bounds in the first paper you cite are completely explicit as you go through the proofs, and can be used to obtain a bound of the form you want. Of course, the constants they write down are a little more complicated than the ones you normally get in e.g. Hoeffding's inequality, but you can always do something a little bit lazy.

2. You can get rather poor bounds without much work by combining the Dvoretzky–Kiefer–Wolfowitz inequality, the Wasserstein duality theorem and a covering argument. An argument would go something like: A. By Wasserstein duality, $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}} | \mu(f) - \hat{\mu}(f) |$ for some `nice' family $\mathcal{F}$. B. By a covering argument, for all $\epsilon > 0$ there exists a finite set $\mathcal{F}_{\epsilon} \subset \mathcal{F}$ s.t. $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}_{\epsilon}} | \mu(f) - \hat{\mu}(f) | + \epsilon$. C. Look at a particular $f \in \mathcal{F}_{\epsilon}$. The Dvoretzky–Kiefer–Wolfowitz theorem gives us a bound on $\P[ | \mu(f) - \hat{\mu}(f) | > \epsilon]$. Taking a union bound over $f \in \mathcal{F}_{\epsilon}$ and applying 2.B gives the result you want.

Unfortunately, I don't remember where to find the `right' covering argument for the 1-Wasserstein distance and the unit square (the details of which Wasserstein distance you're using and the target space make a difference to the efficiency of this bound).

Sorry, I don't have the reputation to comment.

1. Most of the bounds in the first paper you cite are completely explicit as you go through the proofs, and can be used to obtain a bound of the form you want. Of course, the constants they write down are a little more complicated than the ones you normally get in e.g. Hoeffding's inequality, but you can always do something a little bit lazy.

2. You can get rather poor bounds without much work by combining the Dvoretzky–Kiefer–Wolfowitz inequality, the Wasserstein duality theorem and a covering argument. An argument would go something like: A. By Wasserstein duality, $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}} | \mu(f) - \hat{\mu}(f) |$ for some `nice' family $\mathcal{F}$. B. By a covering argument, for all $\epsilon > 0$ there exists a finite set $\mathcal{F}_{\epsilon} \subset \mathcal{F}$ s.t. $W_{1}(\mu, \hat{\mu}) \leq \sup_{f \in \mathcal{F}_{\epsilon}} | \mu(f) - \hat{\mu}(f) | + \epsilon$. C. Look at a particular $f \in \mathcal{F}_{\epsilon}$. The Dvoretzky–Kiefer–Wolfowitz theorem gives us a bound on $P[ | \mu(f) - \hat{\mu}(f) | > \epsilon]$. Taking a union bound over $f \in \mathcal{F}_{\epsilon}$ and applying 2.B gives the result you want.

Unfortunately, I don't remember where to find the `right' covering argument for the 1-Wasserstein distance and the unit square (the details of which Wasserstein distance you're using and the target space make a difference to the efficiency of this bound).