Regarding each given domino as an edge in a graph connecting the vertices labelled from $[![0, k-1]!]$, with "doubles" $\langle j,j\rangle$ handled separately, we need to answer:
* is the graph connected? In general this will be an easy question because most cases will have a much smaller number of vertices than edges. If the answer is "no", the problem sub-divides into the connected components of the graph.
* how many vertices of odd degree are there? This determines the existence of a Eulerian path and so whether all dominoes in the current problem can be included, or otherwise gives initial information to assess which dominoes may need to be excluded. If there are zero or two odd-degree vertices, a Eulerian path is possible and all dominoes can be used.
* for the case where a Eulerian path is not possible, we need to find short paths that link together odd-degree nodes whose removal will not disconnect the graph (but see extra note). These would constitute the dominoes that are not going to be used; the shortest paths that connect pairs of odd-degree nodes (allowing two such to remain) give the dominoes to set aside.
Example adjustment, showing odd-degree nodes in gold and removed edges in red:
Either as given or as adjusted by removal, a Eulerian path can found using e.g. 433
<PERSON>'s algorithm
Handling doubles: These can be kept as a separate list; they are included if there is any other connection to that value (vertex). If consideration is made of which dominoes to ignore, if a double is attached to a node that otherwise has only degree one, this could change the optimum set of dominoes to exclude since the double would also then be unused.
Extra note: finding the paths that connect the odd-degree nodes may not permit keeping the graph connected in some cases, even limiting that to a substantial disconnection (more than just leaving an isolated node), especially if the edges (dominoes) are relatively few and the vertices (values) many. Finding bridges in the graph would allow detection of this case; these can be found in linear time. Example graph: 433