Can we use panels for header and footer? I have a few different top menus which I want to display in certain contexts, and ideally this should go in the header region. However, I have found that Panels can only take over the content region, and the right and left sidebars.

Is there a way to make panels for the header (and footer) regions?

EDIT:
I am using the Bootstrap theme, so I'm not sure if this plays well with the Panels Everywhere theme.
Panels takes over the "Content" region.

Panels everywhere takes over the entire page, and is the module that does what you want.

Some themes are listed on the PE page as "compatible", but all that means is that they ship with appropriate templates, which makes it easier to get started.

You can use any theme you want with PE, but you will likely want to provide your own site-template as alternative to the regular page.tpl.php which PE will disregard. Look at one or two of the themes that are listed on the PE page and their use of template to get started.