How to find coherence between a large number of sentences

You could use clustering with a more basic similarity measure, for example cosine or even simply the proportion of words in common (e.g. Jaccard, overlap coefficient). This should gives you groups of sentences which are "quite similar" against each other, whereas sentences in different clusters are supposed to be very different. This way you would only have to compute WMD distance between smaller groups of sentences. By increasing the number of clusters the clusters would be smaller so there would be less WMD computation needed, however there is more risk to miss a pair of sentences since they could end up in different clusters.