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.