The escape velocity can be found in the usual way from the gravitational potential, but the potential no longer has the pure radial dependence you get with a spherically symmetric assumption. You have to compute the integral
$$ V = -G \iiint \!\!\mathrm{d}x \, \mathrm{d}y \,\mathrm{d}z \, \frac{\rho(x,y,z)}{R} \,,$$
where $\vec{R}$ is the displacement from the point of integration to the point for which the potential s being computed and all three integrals runs over $[-s/2,s/2]$.
That is a bit easier if you put the point of consideration on a symmetry line (through the center of opposed faces or opposed points) but it is pretty grotty any way around. Also recall that there is no particular reason to suspect that the density is either uniform or even nicely varying.
The orbital question is rather more complicated, because while you can still find the orbital velocity that way the stability of orbits is strongly dependent on the higher multipole moments.
Finally, astrophysical objects of sufficient size simply won't have that shape: they are pulled into near-spheroids by their own gravity. The limiting size depends on various assumptions, but self-gravitational roundness is one of the qualification for (dwarf) planet-hood, and the category includes the largest asteroids.