It's probably a little late for this, but I just got into the game and was having trouble with this too.
After screwing up many, many times, I eventually got aboard the ship while they were on the docks. I play very slow and cautiously, so this happens every time for me. I carefully climbed the rigging and... screwed up, and they came onto the ship and fought me.
So what I did was drop a smoke bomb, kill some scrubs, smoke bomb, kill scrubs, and repeat until only the two targets were left. I hit one with a sleep dart, brought the other guy near him, and hit that one with a sleep dart. A short climb half way up the rigging and they were both available for a double air assassination. Easy. Stupid, counterintuitive, and I daresay badly designed for such an objective, but easy.
If you don't mind exploiting AI and implying that in a true historical event Edward Kenway lured two men onto a ship, put them asleep, and then dove at them like some damn lunatic from a story and a half up, go for it. It bugs the living hell out of me to do it this way, but it's done.