I do not understand the problem. Is it a vertical or horizontal menu bar? What do you mean by "filling the page"? The solution could be as simple as setting the div containing the menu to 100% width (or height - as appropriate) and set the background color of the div rather than the anchors. Alternatively, use position absolute and set top and bottom (or left and right) to 0.
As to easy maintenance, I always use PHP include files for headers, footers, menu bars, indeed anything that should appear on all (or multiple) pages. It's fairly simple to do. There is an added complication in that you cannot test your pages locally in your browser. You have to set up a local or remote server 'cos PHP is a server-side language. But once you've set it up, you'll wonder how you ever got by without it.