I think a large group of automorphisms of a curve $C$ only forces
presence of roots of unity in the endomorphism algebra
$\text{End}^0(\text{Jac}\ C)$, so this way is likely to produce
products of abelian varieties with CM by abelian fields. There is a lot
of literature on such examples, e.g. on Fermat curves $x^n+y^n=z^n$, but
they are probably not what you want.
Non-abelian CM seems quite hard to construct explicitly.
It is easiest to work computationally with curves over ${\mathbb Q}$,
and usually in genus 1 or 2.
For $g=1$ all CM fields are imaginary quadratic, and for
$g=2$ they are either abelian quartic or have dihedral Galois group $D_8$.
However, there is a theorem of Shimura that says that $D_8$ examples
do not exist over ${\mathbb Q}$!
To construct such an example over a number field, one can use an approach
of van Wamelen in
`Examples of genus 2 CM curves defined over the rationals'.
This is a very nice paper, where he first shows how to construct such Jacobians
over ${\mathbb C}$ as lattices (sections 2-3). Then he turns to constructing them as genus 2 hyperelliptic curves over ${\mathbb Q}$, which restricts his examples to abelian Galois groups.
(There is a reference to the aforementioned theorem of Shimura on the last page
of the paper.)
One of van Wamelen's examples is carefully worked through in Magma,
in the chapter on
hyperelliptic curves, towards the end in the `From Period Matrix to Curve'
section. A direct link to it is currently
here
but these tend to change with new releases.
It can be adapted to construct a $D_8$ example as well, as follows.
Change the field to ${\mathbb Q}(\sqrt{\sqrt{2}-2})$ in that example
(Galois group $C_4$) by ${\mathbb Q}(\sqrt{2\sqrt{2}-5})$ (Galois group $D_8$).
Then going through that code (plus a little work to get the coefficients as algebraic numbers) gives a hyperelliptic curve with Igusa-Clebsch invariants
$$
[36,45(\sqrt{17} + 1)/2,(729\sqrt{17} - 783)/2,-4\sqrt{17} + 36].
$$
The function HyperellipticCurveFromIgusaClebsch then constructs the curve
in the usual form $y^2=$hexic over ${\mathbb Q}(\sqrt{17})$,
but it has awful coefficients. The example done
in Magma is simplified further using ReducedModel(C: Al:="Wamelen"), but this
function is only implemented over ${\mathbb Q}$.
The field ${\mathbb Q}(\sqrt{17})$ has class number $1$, and the same
ReducedModel algorithm would work over this field, I suppose,
but this is quite a bit of work to implement it properly.
And, if I am not mistaken, in genus 2 this is possibly one of the simplest
examples.
In any case, if you are happy to have examples as lattices in ${\mathbb C}^g$
rather than equations,
then van Wamelen's paper is a good place to look, I think.