OK, you have the Mystaran kraken listed as "working," but I think you can remove the [?] from the language line and call it done. I like that choice.
Want to do the Birthright ones next?
The Brecht priests' claim it's extraplanar in original seems unlikely on the face of it, although I suppose it could be a Fiendish/Half-Fiend/Water-Element Kraken that used to live in the Abyss or the Elemental Plane of Water. That could give it the SR of this monster, but might add more SLAs the original text makes no mention of!
I can go for Native Outsider as you suggest. And it had better be Colossal!
(Heh heh, I have a strange fondness for Colossal+ if you feel inclined to make it really big.)
The average 2E kraken has 90 hp, so this has 2-4/9 times as many hp. The 3E kraken gets 110 hp on average from its HD. If we just use the 2-4/9 multiplier in an approximate way, that should give this thing almost 60d8 for HD (270 hp average). That seems like quite a lot! On the other hand, 30d8 is only 135 hp on average, which seems low. Split the difference at 40 to 50 d8 and just make sure it's got plenty of Con?
I would be willing to consider making it extra large on the Colossal scale.