Alkaline-earth zirconates (CaZrO3, SrZrO3, and BaZrO3) are under active investigation as solid-state electrolytes in hydrogen fuel cells. Their performance as proton conductors depends critically on the properties of acceptor dopants. Here, we use first-principles calculations to study the role of acceptors and point defects in incorporating protons through an oxygen-vacancy-mediated process. For CaZrO3, we find that ZrCa antisites suppress formation of oxygen vacancies. Other intrinsic point defects are shown not to hinder performance. Common unintentional impurities, such as N and C, are not good acceptors but can incorporate in other configurations. Our results show that the effectiveness of common dopants such as Sc and Y is limited by self-compensation due to their incorporation on the "wrong" cation site, where they act as donors. We demonstrate that using alkali metal dopants overcomes this problem, as the formation energy of compensating donors is very high. Alkali metal dopants also have low binding energies for protons, reducing their tendency to act as traps and hence enhancing proton conductivity. Our guidelines for choosing acceptor dopants and optimizing synthesis conditions can greatly improve the efficacy of these proton-conducting oxides as solid-state electrolytes.