Constrained multi-agent partially observable Markov decision processes (CMPOMDPs) represent centrally controlled multi-agent systems operating under partial information and shared cost constraints. The agents must coordinate to (1) maximize their joint return and (2) satisfy the constraint. Prior work has focused on independent agents that only need coordination to satisfy the shared constraint. Such weak coupling allows solutions scalable to many agents, yet is often inappropriate, for instance, when agents act in a shared environment or must explicitly cooperate to maximize their joint rewards. We study locally coordinated systems that capture more expressive coordination based on a joint state while enforcing locality of cost and reward through a coordination graph. To balance (1) expressivity in coordination and (2) scalability for many agents under constraints, we introduce factored-cost partially observable Monte Carlo planning (FC-POMCP). Our empirical evaluation shows that FC-POMCP meets cost constraints and outscales state-of-the-art single-agent baselines.