Recent X-ray observations show absorbing winds with velocities up to mildly-relativistic values of the order of ~0.1c in a limited sample of 6 broad-line radio galaxies. They are observed as blue-shifted Fe XXV-XXVI K-shell absorption lines, similarly to the ultra-fast outflows (UFOs) reported in Seyferts and quasars. In this work we extend the search for such Fe K absorption lines to a larger sample of 26 radio-loud AGNs observed with XMM-Newton and Suzaku. The sample is drawn from the Swift BAT 58-month catalog and blazars are excluded. X-ray bright FR II radio galaxies constitute the majority of the sources. Combining the results of this analysis with those in the literature we find that UFOs are detected in >27% of the sources. However, correcting for the number of spectra with insufficient signal-to-noise, we can estimate that the incidence of UFOs is this sample of radio-loud AGNs is likely in the range f=(50+/-20)%. A photo-ionization modeling of the absorption lines with XSTAR allows to estimate the distribution of their main parameters. The observed outflow velocities are broadly distributed between v_out<1,000 km s^-1 and v_out~0.4c, with mean and median values of v_out~0.133c and v_out~0.117c, respectively. The material is highly ionized, with an average ionization parameter of logxi~4.5 erg s^-1 cm, and the column densities are larger than N_H > 10^22 cm^-2. Overall, these characteristics are consistent with the presence of complex accretion disk winds in a significant fraction of radio-loud AGNs and demonstrate that the presence of relativistic jets does not preclude the existence of winds, in accordance with several theoretical models.