I'm really loving the Khalk'ru vs Mystaran Kraken fight --- it's like a tentacly Godzilla movie!
Unfortunately it'll be one of those
Final Wars type Godzilla battles that are unsatisfyingly short, ending in a few seconds.
Let's do CR 25. You've convinced me.
Your suggested treasure and advancement at 65–128 HD are fine.
I'll go for your proposed "cephalopod rule" for the tentacle attacks, too.
Updating
Mystaran Kraken Working Draft.
Just got the description, background and tactics to sort out!
How about:
A vast mass floats in the water. The mass's greenish-blue colour and frilled surface closely resembles seaweed but then it moves, revealing it to be a living creature of unthinkable size. Piecing together what portions of it can be made out reveal the mass to be an squid-like beast of truly titanic size. Its body is bigger than all but the largest ships and its ten tentacles stretch longer than many city streets.
Mystaran kraken are dim-witted relatives of the common kraken. They are almost unfathomably large, and may be one of the biggest creatures alive. They spend most of their lives in the abyssal depths they call home, but when the hunger or anger of the kraken wakes they can be as devastating as a hurricane, rising to the surface and crushing large ships into splinters with casual ease.
Mystaran kraken are carnivores. They usually hunt by simply reaching out their furlong-length tentacles to snag passing creatures. An immobile Mystaran kraken resembles a floating mass of kelp, and it normally uses this disguise will waiting for unfortunate prey to wander past.
A typical Mystaran kraken has a body 150 feet long and tentacles up to 750 feet long, giving it an "armspan" of 1,600 feet or so.
Mystaran kraken do not speak.
I wasn't sure about the languages. I'd also considered "Mystaran kraken can speak Abyssal and Aquan but almost never talk. Particularly old or intelligent specimens may know additional languages."
Combat
A Mystaran kraken strikes with its tentacles, trying to constrict its opponents and drag them close enough to make bite attacks. If it's seriously injured or loses five or more tentacles it uses its ink cloud and flees the battlefield.