I shall attempt to answer your last question.
Question: Can we tell - and how - whether a given matrix with integer entries (and ∗ eventually) corresponds to a (generalized) regular coloring?
A notion stronger than generalized regular colouring is there in the literature. Given a $q\times q$ matrix $D_q$ whose entries are subsets of $\{0,1,2,\dots\}$ and a graph $G$, a $D_q$-partition of $G$ is a partition of the vertex set of $G$ into sets $V_{i}$ ($1\leq i\leq q$) such that for all $i$ and $j$ every vertex in $V_{i}$ has exactly $D_q(i,j)$ neighbours in $V_j$.
Note: Here $D_q(i,j)$ denotes the $(i,j)$th entry of $D_q$.
The $D_q$-partition problem belongs to the Locally Checkable Vertex Subset and Partitioning problems (LC-VSP) framework of Telle and Proskurowski [1] (also see Telle's thesis Vertex Partitioning Problems: Characterization, Complexity and Algorithms on Partial k-Trees).
Assume that each entry of $D_q$ is either finite or cofinite. Then, there is an FPT algorithm with parameter treewidth (or cliquewidth) to test whether a graph admit a $D_q$-partition. In particular, if the graph has bounded treewdith (or cliquewidth), then we can test in polynomial time. Moreover, the problem also admits a polynomial time algorithm in a number of graph classes including interval graphs, permutaiton graphs, trapezoid graphs, convex graphs and Dilworth-k graphs[2].
It is known that testing for a $D_q$ partition is NP-ocmplete even when the entries are $\{0\}$ or $\{1\}$ (basically adjacency matrix of some graph $H$). In this case a graph $G$ is said to have a $D_q$ partition iff $G$ has a locally bijective homormorphism to $H$ (see [4]). When $H$ is a regular graph, in almost all cases, the problem is NP-complete. Therefore, regular coloring problem is NP-complete.
PS: If every entry in $D_q$ is a set of consecutive integers (true for (generalized) regular colouring), then the problem also fits in the framework of Gerber and Kobler[3]
References
[1] Telle, Jan Arne; Proskurowski, Andrzej, Algorithms for vertex partitioning problems on partial (k)-trees, SIAM J. Discrete Math. 10, No. 4, 529-550 (1997). ZBL0885.68118.
[2] Belmonte, Rémy; Vatshelle, Martin, Graph classes with structured neighborhoods and algorithmic applications, Theor. Comput. Sci. 511, 54-65 (2013). ZBL1408.68109.
[3] Gerber, Michael U.; Kobler, Daniel, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Theor. Comput. Sci. 299, No. 1-3, 719-734 (2003). ZBL1042.68092.
[4] Fiala, Jiří; Kratochvíl, Jan, Locally constrained graph homomorphisms – structure, complexity, and applications, Comput. Sci. Rev. 2, No. 2, 97-111 (2008). ZBL1302.05122.