Here is an example of a $4$-regular, $2$-edge-connected graph with $30$ vertices and no perfect matching, taken from this paper:
The proof that there is no perfect matching is straightforward, Tutte's theorem style: each of the middle vertices can be matched to only one of the outer components, and the other two are left to fend for themselves with an odd number of vertices.
This picture generalizes similarly to how you generalized the bridgeless cubic construction to a $k$-regular construction for odd $k$. In fact, the above graph is slightly more complex than it has to be, because it's planar, which you didn't ask for. The generalization can just have $k-2$ vertices in the center and $k$ petals, each with a single edge to each of the vertices in the center $(k-2)$ edges total.
Then, of course, you need the petals to be $(k-2)$-edge-connected, nearly-$k$-regular graphs (with $k-2$ vertices of degree $k-1$, the remainder of degree $k$) on an odd number of vertices, but that shouldn't be hard. For example, let a petal be made up of three vertex sets $A$, $B$, $C$ of size $k-2$, $k-1$, $2$, respectively: $2k-1$ vertices in total. Each vertex in $A$ is adjacent to each vertex in $B$ - and the vertices in $A$ will also be connected to the center. Each vertex in $B$ is also adjacent to each vertex in $C$, bringing their degree up to $k$; finally, the two vertices in $C$ are adjacent to each other.
The entire graph has $k(2k-1)+(k-2) = 2k^2-2$ vertices, which is an even number.
Best Answer
Use the representation of the $k$-cube as a binary vector of length $k$. For each set of binary digits $b2,\ldots,b_k$ you have an edge between $(0,b_2,\ldots,b_k)$ and $(1,b_2,\ldots,b_k)$.
Now show that this constitutes a perfect matching.