A31 The paladin mark triggers if "it targets any of your allies with an attack power that doesn't include you as a target". It's important to note that this looks at the power, not at an individual attack roll.

The kraken's combo attack (crush twice, devour once) is a single attack power. This is because it has the attack symbol on its statblock. Since the kraken does target the paladin with its combo power, this does not trigger the mark.