First to address the performance issue. Could you confirm that you have TubePress's API cache enabled from WP Admin > Settings > TubePress > Cache? Given your situation it's critical that this is turned on and working.
However, even with the API cache turned on we might still have a performance problem. Since you're asking TubePress to fetch 25 video sources (22 YouTube channels and 3 playlists), there's still a lot of server-side processing that needs to be done. I tested your shortcode on tubepress.com, a moderately high-performance VPS, and the page still took a few seconds to load.
I've tinkered with the idea of adding another cache tier to TubePress that would cache its raw HTML output, but there are a number of caching plugins for WordPress that do just that (e.g. WP Super Cache, WP Fastest Cache). Since you are running W3 Total Cache on your site, I think the best solution would be to simply ensure that your pages with TubePress are being served from W3 Total Cache's cache. Right now it doesn't seem that they are. Thoughts?
Finally, the pagination problem indeed seems to be a new bug. Thank you for reporting this. I'll be investigating tomorrow and will release a fix immediately. Please stand by for an update!