Pandora pays a compulsory streaming rate. Similar to radio they're allowed to play what they like as long as it's not on-demand. Hence you can only skip so many times, and you can't request a specific song. They pay both publishing and performance royalties so rightsholders for the publishing and recording get paid.
Spotify, as an on-demand streaming service, has to negotiate direct deals with rightsholders to use the music. So when you see them paying out a lower rate than Pandora it's because they've traded equity to major labels in exchange for better rates — a very clever way for majors to get money directly from subscribers without needing to distribute it to artists. Independent labels and musicians also need to authorize Spotify, but have less negotiating power so they don't get ownership stakes and have to choose to be completely absent from the system or take the rate offered them.