I'd recommend against Devel::Trace, as Devel:: is mostly concerned with hacking the low-level innards of perl, where your module is more of a "userspace" application. Similarly, Debug::Trace implies some close association with the perl debugger, which is not the case here.

If I were releasing this module, I would probably check with the author of Log::TraceMessages first to see if the two modules could be merged or melded into a common namespace: e.g., Log::Trace and Log::Trace::Messages. If there isn't any common ground, perhaps Log::Trace is the best option so far.

For your second module, I reiterate Debug:: and Devel:; as being inappropriate top-level domains Since the module is most closely associated with Test::Harness, perhaps Test::Assertions would be best.

One other place to check naming issues before you upload may be modules@perl.org. See section 2.5 of The Perl5 Registered Module List for details.