We investigate theoretically the prospects for using a magnetic nanoelectromechanical single-electron tunneling (NEM-SET) device as an electronic spin filter. We find that strong magnetic exchange forces on the net spin of the mobile central dot of the NEM-SET structure lead to spin-dependent mechanical displacements ("spin polarons"), which give rise to vastly different tunnelling probabilities for electrons of different spin. The resulting spin polarization of the current can be controlled by bias and gate voltages and be very close to 100% at voltages and temperatures below a characteristic correlation energy set by the sum of the polaronic and Coulomb blockade energies. ; Comment: Accepted for publication as a Rapid Communication in Phys. Rev. B and selected as an "Editors' Suggestion" paper. This version has minor modifications compared to arXiv:1205.2979, which it replaces