Half damage to the body from severing tentacles is ok.
I can also go with the revised Camouflage text and the proposed Shipcrusher ability.
Updating
Mystaran Kraken Working Draft.
Any other SAs, or are we ready for skills and feats?
I did wonder about tweaking the Camouflage to allow the Kraken to substitute a Hide or Disguise check for the flat DC, similar to the SRD Mimic.
Kelp Mimicry (Ex): A Mystaran kraken can rest motionless and almost perfectly mimic a floating mass of kelp. Anyone who observes a camouflaged Mystaran kraken can detect the ruse with a successful Spot check opposed by the kraken's Hide check. A Mystaran kraken can take 10 on a kelp mimicry Hide check and normally does so, giving the Spot check a DC of ??. Unfortunate creatures may already be within reach of the kraken's tentacles before they see it. If the Mystaran kraken moves it immediately reveals itself. Creatures with ranks in Knowledge (arcana) or Survival may use one of those skills instead of Spot to notice the monster.
or are we ready for skills and feats?
We might as well start talking about them.
If we use the Kelp Mimicry above I was thinking we'd give it a hefty racial bonus to kelp mimicry of +12.
I'm inclined to split the skill points between Spot and Listen with the extra point in Spot, like the SRD Giant Squid. I'll assume it has the Alertness feat, since the Squid and all giant Cephalopods have it.
Also, since these things appear to be giant octopi rather than squid I'm inclined to give them the racial skill bonuses of an Octopus:
Skills #1: Escape Artist +13, Hide +5 (+13 kelp mimicry), Listen +38, Spot +39, Swim +29
Skills: A Mystaran kraken can slightly change its color and shape, giving it a +4 racial bonus on Hide checks. *When using its kelp mimicry power, the Hide bonus improves to +12. A Mystaran kraken also can squeeze and contort its body, giving it a +10 racial bonus on Escape Artist checks.
A kraken has a +8 racial bonus on any Swim check to perform some special action or avoid a hazard. It can always choose to take 10 on a Swim check, even if distracted or endangered. It can use the run action while swimming, provided it swims in a straight line.
Alternatively, we could trim the Listen and Spot down to +30 to match the SRD Kraken and put those points in Hide to give it a more CR appropriate skill level:
Skills #2: Escape Artist +13, Hide +22 (+30 kelp mimicry), Listen +30, Spot +30, Swim +29
Skills: A Mystaran kraken can slightly change its color and shape, giving it a +4 racial bonus on Hide checks. *When using its kelp mimicry power, the Hide bonus improves to +12. A Mystaran kraken also can squeeze and contort its body, giving it a +10 racial bonus on Escape Artist checks.
A kraken has a +8 racial bonus on any Swim check to perform some special action or avoid a hazard. It can always choose to take 10 on a Swim check, even if distracted or endangered. It can use the run action while swimming, provided it swims in a straight line.
Hmm… I quite like that.
For the feats, I'd take Alertness, Blind-Fight, Improved Critical (tentacle), Improved Initiative, Improved Trip and Iron Will from the Kraken and Diehard and Endurance from the Giant Squid.
Add Combat Reflexes, Dire Charge, Epic Will, Improved Critical (bite), and Weapon Focus (bite, tentacle) to buff out its combat abilities.
Let's see, that's 14 feats so we've still got eight more to pick. I'm not seeing that much else I'm really enamoured for this creature. Devastating Critical would seem a really munchkin option - the save to avoid instant death would be Fort DC 63!
Maybe some of the other combat feats - Superior Initiative, Multiattack and Improved Multiattack, Great Fortitude, Lightning Reflexes, Power Attack, Cleave, Great Cleave would make eight but they're pretty much the "usual suspects".