How to best warm the cache
Varnish is sometimes used to paint over poorly written code.  It's not horrible to get it up and running, but it seems to me that in this case, it might just be easier to fix the poorly written code.

I believe that what cache warmer does is it pings all of the URLs to get the caches to regenerate... but that just triggers the cache rebuilding process, which isn't instantaneous with Craft CMS.  Did you try waiting a little bit?

Does the data in the large structure change that often?  Something else you could consider too is putting the left menu in a its own template that you cache and load via AJAX so that the rest of the page isn't waiting for it.