A straightforward extension of the McNemar test for paired binary data yields an exact test for the equality of the limiting marginal distributions for bivariate binary Markov chains. The exact distribution of the test statistics under the null hypothesis of equal marginals depends on the classical cell occupancy statistics for the Bose-Einstein model. Exact p-values are computed for the one-sided test, and the mean and variance of the test statistic are found. The power of the Markov-McNemar test is found to be close to the power of the classical McNemar test for independent paired observations when the independence assumption holds. The method is applied to the comparison of ribosomal DNA sequences.