Spinel (MgAl_2_O_4_) and krotite (CaAl_2_O_4_) are alternative candidates to alumina (Al_2_O_3_) as primary dust condensates in the atmospheres of oxygen-rich evolved stars. Moreover, spinel was proposed as a potential carrier of the circumstellar 13um feature. However, the formation of nucleating spinel clusters is challenging; in particular, the inclusion of Mg constitutes a kinetic bottleneck. We aim to understand the initial steps of cosmic dust formation (i.e. nucleation) in oxygen-rich environments using a quantum-chemical bottom-up approach. Starting with an elemental gas-phase composition, we constructed a detailed chemical-kinetic network that describes the formation and destruction of magnesium-, calcium-, and aluminium- bearing molecules as well as the smallest dust-forming (MgAl_2_O_4_)1 and (CaAl_2_O_4_)1 monomer clusters. Different formation scenarios with exothermic pathways were explored, including the alumina (Al_2_O_3_) cluster chemistry studied in Paper I (Gobrecht et al., 2022A&A...658A.167G, Cat. J/A+A/658/A167) of this series. The resulting extensive network was applied to two model stars, a semi-regular variable and a Mira-type star, and to different circumstellar gas trajectories, including a non-pulsating outflow and a pulsating model. We employed global optimisation techniques to find the most favourable (MgAl_2_O_4_)n, (CaAl_2_O_4_)n, and mixed (Mg_x_Ca_(1-x)Al_2_O_4)n isomers, with n=1-7 and x in [0..1], and we used high level quantum-chemical methods to determine their potential energies. The growth of larger clusters with n=2-7 is described by the temperature-dependent Gibbs free energies. In the considered stellar outflow models, spinel clusters do not form in significant amounts. However, we find that in the Mira- type non-pulsating model CaAl_2_O_3_(OH)2, a hydroxylated form of the calcium aluminate krotite monomer forms at abundances as large as 2x10^-8^ at 3 stellar radii, corresponding to a dust-to-gas mass ratio of 1.5x10^-6^. Moreover, we present global minimum (GM) candidates for (MgAl_2_O_4_)n and (CaAl_2_O_4_)n, where n=1-7. For cluster sizes n=3-7, we find new, hitherto unreported GM candidates. All spinel GM candidates found are energetically more favourable than their corresponding magnesium-rich silicate clusters with an olivine stoichiometry, namely (Mg_2_SiO_4_)n. Moreover, calcium aluminate clusters, (CaAl_2_O_4_)n, are more favourable than their Mg-rich counterparts; the latter show a gradual enhancement in stability when Mg atoms are substituted step by step with Ca. Alumina clusters with a dust-to-gas mass ratio of the order of 10^-4^ remain the favoured seed particle candidate in our physico-chemical models. However, CaAl_2_O_4_ could contribute to stellar dust formation and the mass-loss process. In contrast, the formation of MgAl_2_O_4_ is negligible due to the low reactivity of the Mg atom.