I haven't used Business::Paypal::SDK in particular, but that error is typical of not having your CLASSPATH setup properly.

I would write a little test java program that uses the paypal Java code - at least then you'll only need to worry about the perl side of things.