I wondered how you know Mary's surname, have you confirmed with other records that John did marry a Mary Brag.
It might also be worth searching using spelling variations of the surnames. Also remember that not all parish registers are index or available on any of the sites.
Devon FHS have indexed marriage for 1754 to 1837 and I think it covers all of Devon, at least where registers have survived or been deposited in one of the Archives. This can be accessed in the Members' Area of the website by DFHS Members.
It's also possible that they did not marry in Devon.