Most of the provices all over the mediterranean are capable of training at least a limited amount of Roman troops. But you need a lvl 2 government building, which takes 14 turns to build. If you have the time, you must build this type of building to be able to recruit anything more than regional troops. Since you have taken over Macedon, build at least one of these buildings in the largest province you have conquered, both to maximize the amount of troops you can recruit and to ensure better population loyalty.