Some bandits are requiring tolls to cross the bridges into Ile de la Cite and need to be put in their place.
The southeast Captain is in a house in a small restricted zone and if you have Disguise it is easy enough to get to the Captain. If you don’t have the ability then climbing the western buildings, dropping off the east side and entering a small alley next to the building with the Captain is the best approach. From the alley you can hide on the fence and then use the crowd to blend in before hopping into the window to kill the Captain.
The southwest Captain takes a long patrol rather close to the end of the restricted zone, but wait until he turns away to double assassinate the two guards before using the crowd to sneak up on him and kill him.
The northwest Captain is the easiest to kill by simply approaching from the south and sniping him with a headshot. You can then take out the bodyguards or drop off the bridge to escape.
The northeast Captain walks a short route on the northern end of the bridge. If you approach from the south and hug the right wall you should be able to climb the building and jump into the haycart on the other side. Wait for the Captain to pass, walking north, and hop out and follow him for a clean kill.
A gang is robbing graves in the Ile de la Cite graveyard and a letter protects them from arrest.
Make your way to the restricted zone and climb the buildings in the northeast, but don’t use Eagle Vision or he will run. Once in the right spot, wait for the Brute to walk away and then air assassinate the other single man and steal the letter. You can then use the lift to quickly escape the guards and complete the mission.