I test every method before its called with can_ok, and I (re)test the same method on each instance I create. Sometimes I actually set up test_Object_Interface functions and use it to test subclasses (which is the source of many of the duplicate tests).

I would not do this. If the methods are called once and succeed, that should be enough. Testing with can() is not very useful, since that isn't really calling the interface to your class.

I test all my constants using can_ok and then test their value.

I don't see how you could do that without embedding the values of the constants in your test, which would be wrong. Unless these constants are a part of your public API, you should not be testing them at all.