If you want to use pure FME I'm afraid adding a legend is going to take a lot of fiddling around with transformers and using a template is not possible.o
You may be interested in FME Auto, that's an extra-cost plug-in for FME and Avenza's MAPublisher. MAPublisher is a GIS/cartography plug-in for Illustrator, so you'll need a license of that too. This has a number of benefits, such as being able to use a template, having all the styling done by MAPublisher (which is a lot easier than PDFStylers in FME). I'm not sure whether legend creation can be scripted too but I can find out if you want. I'm not sure it's the right solution for you but it's worth looking into I think.
it is possible to use a template to control everything prior to sing a pdf formatter (you don't need to use formatter even).
Number of layers is not a real issue either.
Legend creation parallel to content control is possible, just a little complexish.