A new Korteweg-de Vries type of equation for uni-directional waves over slowly varying bottom has been derived in Part I. The equation retains the Hamiltonian structure of the underlying complete set of equations for surface waves. For flat bottom it reduces to the standard Korteweg-de Vries equation. Uniform travelling waves (solitary and cnoidal waves) that exist when the bottom is flat will distort over a varying bottom. In this paper, the distortion of periodic and solitary travelling waves will be studied. The distortion is in the first instant approximated by a quasi-homogeneous succession of uniform waves, each one being determined by specifying the horizontal momentum (and hence the amplitude) at the location of the wave. The changing value of the momentum with position is found first from energy conservation. For periodic, cnoidal waves, for which the mass vanishes, the change of wavelength has to be taken into account; some numerical results are given. Solitary waves carry a mass that depends on the amplitude (momentum) and the quasi-homogeneous approximation has to be modified to satisfy mass-conservation. This is achieved by introducing an additional parameter in the base functions with which the distortion is approximated. Instead of using pure solitary waves, one modification consists of adding a tail of finite, but varying length and amplitude. When the bottom decreases sufficiently fast far away from the wave, an alternative description of the distortion will be presented as a succession of solitary waves above a varying, non-flat equilibrium elevation of the surface. In both cases, the dynamic equations obtained from energy and mass conservation differ in essential order from the result without modification.