Substitutions on words, \emph{i.e.}, non-erasing morphisms of the free monoid, are simple combinatorial objects which produce infinite words by replacing iteratively letters by words. This paper introduces a notion of substitution acting on multi-dimensional words, namely the \emph{local rule substitutions}. Roughly speaking, \emph{local rules} play for multi-dimensional words the role played by the concatenation product for substitutions on words. We then particularly focus on the local rule substitutions which act on the $2$-dimensional words coding \emph{stepped surfaces}, and we show that a wide class of them can be derived from \emph{generalized substitutions}.