We consider a lattice model of itinerant electrons coupled to an array of localized classical Heisenberg spins. The nature of the ground-state-ordered magnetic phases that result from the indirect spin-spin coupling mediated by the electrons is determined as a function of density and the spin-fermion coupling J. At a fixed chemical potential, spiral phases exist only up to values of J which are less than roughly half the electronic bandwidth. At a fixed electron density and near half filling, the system phase-separates into a half-filled antiferromagnetic phase and a spiral phase. The ferromagnetic phases are shown to be fully polarized, while the spiral phases have equal admixture of up and down spins. Phase separation survives in the presence of weak pairing field Δ but disappears when Δ exceeds a critical value Δc. If pairing fields are large enough, an additional spiral state arises at strong coupling J. The relevance of this study, especially the phase separation, to artificially engineered systems of adjacent itinerant electrons and localized spins is discussed. In particular, we propose a method which might allow for the braiding of Majorana fermions by changing the density and moving their location as they are pulled along by a phase separation boundary.