> Why don't the rules fire,

Because the 'match' is at the wrong type.

This was the correct hint, thanks!
 
> what can I change such that they do,

Type signatures.

Initially, I thought that just leaving out the polymorphic signature should fix the problem. But I think it cannot be fixed by changing type signatures only because once the type of `g` in the rule is fixed, the rule is no longer type correct!

To overcome this, I have defined

    gen :: (forall m . Monoid m => (a -> m) -> b -> m) -> b -> [a]
    gen g = g single
    {-# NOINLINE gen #-}

and changed the rules to

{-# RULES
  "monoid fusion pointfree"
    forall f (g :: forall m . Monoid m => (a -> m) -> b -> m) .
      fold f . gen g = g f;

  "monoid fusion pointed"
    forall f (g :: forall m . Monoid m => (a -> m) -> b -> m) b .
      fold f (gen g b) = g f b;
  #-}

and now they fire. Seems a bit roundabout but I don't see how to avoid this indirection.
 
> and what to get rid of the warning for the second rule (which I think
> is the one I should use)?

I'll let that for somebody else.

My new rules don't cause this warning. I'm still interested in what the warning meant, although my code does not depend on an answer anymore.

Probably because, GHC inlines function composition in the first line of

    main = do print ((fold id . gen idGen) [[()]])
              print (fold id (gen idGen [[()]]))

the pointed rule fires twice if I remove the point-free one.

Does it make sense to keep the point-free rule just in case that `fold f . gen g` is passed to a higher-order function and does not get an argument after inlining?

Sebastian