Johne’s disease (paratuberculosis), a worldwide enzootic disease of cattle caused by Mycobacterium avium subsp. paratuberculosis (Map), mainly introduced into farms by purchasing infected animals, has a large economic impact for dairy producers. Since diagnostic tests used in routine are poorly sensitive, observing Map spread in the field is hardly possible, whereas there is a need for evaluating control strategies. Our objective was to provide a modelling framework to compare the efficacy of regional control strategies combining internal biosecurity measures and testing of traded animals, against Map spread in a metapopulation of dairy cattle herds. We represented 12,857 dairy herds located in Brittany (France), based on data from 2005 to 2013, used to calibrate herd sizes and demographic rates and to define trade events in a multiscale model of Map infection dynamics. By clustering and categorical descriptive analysis of intensive simulations of this model, based on a numerical experimental design, a large panel of control measures was explored. Their efficacy was assessed on model outputs such as the prevalence and probability of extinction at the metapopulation level. In addition, we proposed a scoring for the effort required to implement control measures and prioritized control strategies based on their theoretical epidemiological efficacy. Our results clearly indicate that eradication cannot be achieved on the mid term using available control measures. However, we identified relevant combinations of measures that lead to the control of Map spread with realistic level of implementation and coverage. The study highlights the challenge of controlling paratuberculosis in an endemically infected region as related to the poor test characteristics and frequent trade movements. Our model lays the foundations for a flexible and efficient tool to help collective animal health managers in defining relevant control strategies at a regional scale, accounting for local specificities in terms of contact network and farms’ characteristics.