Can CPAN code be based on Graphics::Magick? Why not? It works for you, you want to share it, I don't see any issue. :-)

Should such code look for either module and switch? If it works, and you want to do so, be my guest. I don't see that as a prerequisite.

Test graphics modules? I'm not sure. Have you looked at, for example, unit tests for GD? Or any other graphic-output module? That's where I'd start looking.