We explore some of the consequences of Dark Matter-photon interactions on structure formation, focusing on the evolution of cosmological perturbations and performing both an analytical and a numerical study. We compute the cosmic microwave background anisotropies and matter power spectrum in this class of models. We find, as the main result, that when Dark Matter and photons are coupled, Dark Matter perturbations can experience a new damping regime in addition to the usual collisional Silk damping effect. Such Dark Matter particles (having quite large photon interactions) behave like Cold Dark Matter or Warm Dark Matter as far as the cosmic microwave background anisotropies or matter power spectrum are concerned, respectively. These Dark Matter-photon interactions leave specific imprints at sufficiently small scales on both of these two spectra, which may allow to put new constraints on the acceptable photon-Dark Matter interactions. Under the conservative assumption that the abundance of 10^12 M_sol galaxies is correctly given by Cold Dark Matter, and without any knowledge of the abundance of smaller objects, we obtain the limit on the ratio of the Dark Matter-photon cross section to the Dark Matter mass sigma_{gamma-DM} / m_DM < 10^-6 sigma_Thomson / 100 GeV \sim 6 * 10^-33 cm^2 GeV^-1 .

14 pages, 5 figures, to appear in PRD