This is possible for any $g$ and $k$. The idea is as follows:

(1) Start with a dessin embedded in the sphere $S^2$ with symmetry group $C_k$ which has a lot of faces and a lot of triple points.

(2) Make a surgery on the surface at a collection of triple points that are far away.

When you do (2) there faces adjacent to one vertex will become one face, so the Euler characteristic of your surface will drop by $2$ and genus will increase by $1$.

It a bit hard to describe this surgery in words, but the idea is the following: to each dessin embedded in a surface you can associate its thinking, that is called a ribbon graph, or a fat graph. And a ribbon graph defines the surface. Now, in order to associate the structure of a ribbon graph to a abstract graph one has to choose a cyclic order on the edges at each vertex. And the surgery in (2) amounts just to changing the cyclic order at exactly one vertex. 

I attach a picture which describes the above procedure. There is a honeycomb graph there with one surgery at one point. [![enter image description here][1]][1]


  [1]: https://i.sstatic.net/BFw2H.jpg