Well, this is certainly a new one! I've never even dreamed of using PadWalker with a Safe compartment before :-)
I'm not familiar with the details of how Safe works internally, but it's almost certainly fair to say that PadWalker will need to be modified to detect the Safe compartment and behave appropriately. In other words you'll need to dirty your hands with perlguts a little, to make this work. Probably.
The only other idea I have is that it might work if you can load PadWalker and Devel::Trace inside the same Safe compartment as the code you're executing. Have you tried that?