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]

Here is one more picture, with a slightly different construction, if one glues two "disk-like" surfaces in the picture one gets a surface of genus $2$ with a dessin that has a $C_3$ symmetry (i.e. the example you mentioned). Here you start with a dessin of $S^2$ that has a $C_3$. This  symmetry and then flip two vertex. The sphere is glued from two disks and you flip on vertex in each disk (it is red on the picture). Flipping one point increases genus by $2$. It changes the structure of ribbon graph, but doesn't change the dessin. This picture generalises to any $k, g$. [![enter image description here][2]][2].


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