well, I would imagine that the best way to enlarge would be horizontally, if you already aren't set up that way. The only thing about making prints that big is maintaining a water bath for the trays to keep temperature. Using trays for color is definitely possible, but without a watchful eye and a good thermometer, it can be a bit of a headache =(. As to a color head being a must, I would strongly recommend it versus color packs, being that you can dial in almost exact color values with it, versus a little more of a "sticks and stones" method with color packs, IMO. Regarding paper, if you want to go up to 40 inches(long side), you can likely purchase roll stock of fuji and kodak papers, I don't know if there is a purchase minimum, many shops that can get it usually have a minimum order, etc... Kodak and Fuji both have a good selection of roll media. (Fuji super gloss is one of my favorites for when i make big prints).
Have you considered scanning and getting a lightjet print made? It would be on the same kind of paper that you could use in your own darkroom, but with the great control of using photoshop. Especially for a print up to 40". And with the file, you can play with it as much as you want.
Whichever way you go, best of luck with it!!!