Subroutines are compiled when the their source file is initially encountered. For the main source file and any modules that are called through "use", this means at startup. (On the other hand, "require and "new" are run time statements.)
Method calls have a little bit of additional overhead, because perl needs to search the @ISA chain and find the package of the ancestor class which contains the method. On the first call to a method, perl caches the package that contains the subroutine, speeding things up for subsequent calls.
The UNIVERSAL::can() method can perform this lookup, and I believe it performs the same caching as the inital method call.
You are correct. UNIVERSAL::can() does use the normal method caching mechanism (depth-first, leftwards). Run-time inheritance changes are reflected in it.