The divisibility_test is just a (lexical) coderef, not an object method, so you haven't really replaced any object methods.

Also your _init method does not need to have the $divisor passed to it because you could just retrieve it by dereferencing $instance.

Once you call set_divisibility_test(), your default divisibility_test is lost, with no way to get it back. It may be better to handle this by letting divides() take an optional coderef and use your default one if none is supplied.

And you'll need a DESTROY method to remove $divisibility_test_for{$self} when the object goes out of scope, or you'll be leaking memory.