Sorry, I don't have the reputation to comment.
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.
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).