Thank you, MigMit!
If I replace your type FoldSTVoid with:
data FoldMVoid = FoldMVoid {runFold :: Monad m => (Int -> m ()) -> m ()}
then everything works magically with any monad!
That is exactly what I wanted, though I still do not quite understand why wrapping the type solves the problem
Short answer: It's because GHC's type system is predicative.
Basically, quantified types can't be given as arguments to type constructors (other than ->, which is its own thing). I'm not entirely sure why, but it apparently makes the type system very complicated from a theoretical standpoint. By wrapping the quantified type in a newtype, the argument to IO becomes simple enough not to cause problems.