Effect of water pressure on sinking objects

That is right, deeper the pressure is stronger. But the pressure is not just in one direction it is in every direction. So the velocity will decrease in most cases. But also you have to be aware of the density of the object. You could read this classical description of diving objects "Thrust" on wikipedia. This is a classical effect, in real cases the relation between deepness and pressure is not always linear.

Here is an example of the every direction pressure.

And answering the other question. That is possible under some specific conditions. You could have solid water. But I don't know exactly if our planet is capable of have that rare condition. In addition I have found information of a exoplanet that matches those conditions NatGeo.

Regards.

If You make a simplified force balance of a sinking box, You can identify two main forces: Force associated with box's weight $F_g$ acting downwards and buoyancy force $F_b$ acting upwards. The formulas are as follows:

$F_g=mg$,

$F_b=-\rho g V$,

where $m$ is the mass of the box, $g$ is the gravitational acceleration, $\rho$ is the density of water, $V$ is the volume of the box.

The buoyancy force is a result of superposition of two forces associated with pressure: force acting on the bottom of the box and force acting on the top of the box:

$F_b=p_tS-p_bS=\rho g HS-\rho g (H+h)S=-\rho g h S=-\rho g V$,

where $p_t$ is the pressure on top of the box, $p_b$ is the pressure on the bottom of the box, $H$ is the distance from the water surface to the top side of the box and $h$ is the box's height. I assume that the top and bottom side of the box has the same area $S$.

Now the balance is:

$F_t=F_g-F_b$

assuming that the axis goes downwards.

$F_t=mg-\rho gV$

When the depth ($H$) increses, the density of water also increases and therefore the total force draging the box down should decrease if we assume that $V$ is constant. So it looks like the acceleration should decrease in this case. If You consider viscosity forces, dynamic viscosity of water increases with pressure, so it should further slow down the box, but I don't know to what extent.

When it comes to Your second question, the melting point of water decreases with increasing pressure, as it is shown here:

As You can see, the water at the bottom of an ocean should have the temperature much below 0 Celsius degree to solidify, so this isn't really probable. According to wikipedia the temperature of deep ocean water varies from 0 °C to 3 °C.