I will think of $X$ as the set of allowed degree values, with largest value being $b$, and the total number of elements of $M$ to be $m$.
If $m=1$ with nonnegative value $b$ as the sole member, then you will need $k$ to be $b+1$, as that many vertices are needed for a graph with vertex of degree $b$. In general, an optimal value for $k$ will be less than $b$, and characterizing those $M$ which need an optimal $k\geq b$ might be a good exercise which I do not do here. The construction I describe below will work for $b$
sufficiently large (likely $b \gt 1$); I leave the details of small $b$ to others.

Let there be a set of $n$ vertices and $k$ a positive integer with $n \geq 2k+1$.
Arrange them in a circle, and consider $n$ subsets of adjacent $k+1$ vertices. (If we were to label them from $0$ to $n-1$, the "smaller" difference modulo $n$ of any two labels from this subset should be at most $k$.) The graph $W_{n,2k}$ given by the $n$ vertices and the set of edges being all two element subsets of any of the $n$ subsets is a regular graph of degree $d=2k$. If $n$ is even, there is a matching of vertices that form edges outside of $W_{n,2k}$ which gives a regular graph of degree $d=2k+1$.
If $n$ is odd and $2k + 1 \lt n$, there is a partial matching which gives a graph that
is almost regular of degree $d=2k+1$, with one vertex of degree $2k$. We will collect
all these graphs and graph fragments and call them $F_{n,d}$, where a graph fragment is like a graph but may have one or more "dangling" edges. Except for this minor detail of sometimes leaving an edge dangling, the $F_{n,d}$ would look like regular graphs of degree $d$ on $n$ edges.

Let us consider a second construction of a certain "bipartite" portion of a graph. Arrange $n$ red points in a circle, and arrange $n$ blue points in a circle corresponding to the red points. I will be constructing a drum graph. Given $k\leq n$, for each red point connect it (add an edge) to $k$ blue points which are the point "below" that red point and the next $k-1$ blue points in a clockwise orientation. This will produce a regular bipartite graph of degree $k$ on $2n$ vertices, which I call $D_{2n,k}$. Notice we can later add edges between red vertices or between blue vertices.

I use these to inspire a suboptimal construction for $M$ in which $k \leq b+2$; later I will show how to improve it to reduce $k$. Consider a set of vertices containing the same number of elements as elements of $M$. Turn this into a graph fragment by associating $d$ edges for the element corresponding to (the image under $f$ of) $d \in X$. I will call this a column, and for the moment I will in the construction insist that no two elements in a column are joined by an edge.

I start by applying the fragment construction $F_{k,d}$ in parallel. This means for each vertex I construct a (disjoint) graph fragment using $F_{k,d}$. I now have $km$ many vertices. If I chose $k$ large enough, I could finish off the construction by choosing $k=2b$. We can do better though.

Suppose we choose $k = \lceil (b+1)/2 \rceil$. For many of the vertices the $F_{k,d}$ construction will result in graph fragments with many edges left over. In particular, if we try $F_{k, b}$ for this choice, we have $k$ vertices of degree $k-1$ instead of $k$ vertices of degree $b$. No problem: we now apply the $D_{2k,b+1-k}$ construction, and duplicate this fragment and use the drum construction to pair things up. Thus for each vertex coming from an element of $M$, I have a combination of a red $F_{k,d}$, a blue $F_{k,d}$ and the bipartite portion $D_{2k,d+1-k}$ and thus handle that degree. (When $F_{k,d}$ is a graph and not a fragment, we duplicate it but the $D$ portion will have no edges.) Thus we can create a graph for $M$ with $k \leq b+2$.

Note in the above we only connected edges between vertices associated with exactly one element of $M$: we never added an edge between vertices at two different "levels" of a column or even different levels between two columns. If $M$ has more than one element, you can reduce the value of $k$ needed by connecting column elements to one another to reduce the value of $b$ and thus of $k$ needed. Further, after doing the $F_{k,d'}$ construction ($d'$ is now the number of dangling edges for each vertex in the column), you can connect the various $F_{k,d'}$ together. If you still have an edge left over, duplicate the whole fragment and join edges together. Because $M$ has more than one element, each maximal degree element can be connected to something (assuming $b$ large enough), and this means that the required $k$ is reduced to a value usually much less than $b$.

Gerhard "Who Was That Masked Person?" Paseman, 2015.10.30