A pure quantum state of N subsystems with d levels each is called k-multipartite maximally entangled state, which we call a k-uniform state, if all its reductions to k qudits are maximally mixed. These states form a natural generalization of N-qudit Greenberger-Horne-Zeilinger states which belong to the class 1-uniform states. We establish a link between the combinatorial notion of orthogonal arrays and k-uniform states and prove the existence of several classes of such states for N-qudit systems. In particular, known Hadamard matrices allow us to explicitly construct 2-uniform states for an arbitrary number of N>5 qubits. We show that finding a different class of 2-uniform states would imply the Hadamard conjecture, so the full classification of 2-uniform states seems to be currently out of reach. Furthermore, we establish links between the existence of k-uniform states and classical and quantum error correction codes and provide a graph representation for such states.