Relativistic laser interaction with micro-and nano-scale surface structures enhances energy transfer to solid targets and yields matter in extreme conditions. We report on the comparative study of laser-target interaction mechanisms with wire-structures of different size, revealing a transition from a coherent particle heating to a stochastic plasma heating regime which occurs when migrating from micro-scale to nano-scale wires. Experiments and kinetic simulations show that large gaps between the wires favour the generation of high-energy electrons via laser acceleration into the channels while gaps smaller than the amplitude of electron quivering in the laser field lead to less energetic electrons and multi-keV plasma generation, in agreement with previously published experiments. Plasma filling of nano-sized gaps due to picosecond pedestal typical of ultrashort pulses strongly affects the interaction with this class of …