Interaction of Re, Ta, W and Mo solutes with vacancies and their diffusion in fcc Ni is investigated by density-functional theory in combination with kinetic Monte Carlo simulations. Interaction energies are calculated for the first six neighbor shells around the solutes and a complete set of diffusion barriers for these shells is provided. Further, diffusion coefficients for the four elements in Ni as well as for vacancies in the presence of these elements are calculated. The calculated solute diffusion coefficients based on our ab initio data are found to compare favorably to experimental values. The mobility of the vacancies as a key factor in dislocation climb is only minimally influenced by the solute atoms within the dilute limit.