The rapid diffusion of Artificial Intelligence (AI) across higher education institutions (HEIs) in Africa is fundamentally reshaping the expectations, competencies, and responsibilities of educational leaders. While AI offers transformative possibilities -- from personalized learning and administrative efficiency to evidence-based governance -- its responsible integration demands proactive, contextually grounded leadership and robust institutional policy frameworks. This article examines the intersection of AI adoption and educational leadership in African higher education, with a particular focus on the policy implications for university administrators, academic managers, and national policymakers. Drawing on a systematic review of more than fifty peer-reviewed sources, policy documents, and practitioner reports, the authors argue that effective AI governance in African HEIs requires leaders who possess not merely technical awareness but deep competencies in digital ethics, epistemic justice, equity-centred decision-making, and transformational change management. The article identifies critical policy gaps at both institutional and national levels, analyses the risk of digital colonialism embedded in uncritical AI adoption, and advances a comprehensive framework for AI-responsive educational leadership tailored to the African context. Special attention is given to academic integrity, faculty capacity building, data sovereignty, and the imperative to foreground African knowledge systems in AI-mediated educational environments. The article contributes original theoretical and applied insights to the growing field of AI in African higher education, and provides actionable recommendations for leaders navigating this complex terrain.