Check Net::OpenSSH and Net::SSH::Parallel. Both can be used to run commands through sudo easily.

Net::SSH::Mechanize also claims to support sudo natively.