Ballistic transport of helical edge modes in two-dimensional topological insulators is protected by time-reversal symmetry. Recently it was pointed out [1] that coupling of non-interacting helical electrons to an array of randomly anisotropic Kondo impurities can lead to a spontaneous breaking of the symmetry and, thus, can remove this protection. We have analyzed effects of the interaction between the electrons using a combination of the functional and the Abelian bosonization approaches. The suppression of the ballistic transport turns out to be robust in a broad range of the interaction strength. We have evaluated the renormalization of the localization length and have found that, for strong interaction, it is substantial. We have identified various regimes of the dc transport and discussed its temperature and sample size dependencies in each of the regimes.