Blocking ads in Pandora Radio app turns out to be as simple as setting up these custom rules in Weblock:

URL regular expression: *.pandora.com/*/ads/*
URL regular expression: *.pandora.com/*getadmetadata*
URL regular expression: *.pandora.com/*registerad*

Since we are unable to fully test this solution (Pandora works only in US, Australia and New Zeland), we'll appreciate your feedback. We've tested this via VPN connection to server located in the US, and the ads are really gone. Please let us know if the above worked for you.

Update: For your convenience, we've created a separate rule for blocking ads in Pandora app in the Filters tab inside Weblock. There is no need to create custom rules to block these ads anymore.