Here's an alternative take on the problem: one may use Theorem 2.1 from nLab's article on the free monoid (note: $\operatorname{Mon}(\mathsf{C})$ means the category of monoids in a monoidal category $\mathsf{C}$) and then apply Lemma 5.1.3 of Riehl's book (saying that any functor adjunction induces a monad on the domain of the left adjoint). A proof of the mentioned Theorem 2.1 of the nLab's article may be read in Mac Lane's Categories for the Working Mathematician, VII.3, Theorem 2. Anyway, here's a proof outline:
We define a left adjoint $F:\mathsf{C}\to\mathrm{Mon}(\mathsf{C})$ to the forgetful functor $\mathrm{Mon}(\mathsf{C})\to\mathsf{C}$. It sends $c$ to $Fc=\sum_{n\geq 0}c^{\otimes n}$. The unit $\eta=i_0:*\to Fc$ is just the inclusion in degree $0$. Distributivity of the tensor product with respect to countable coproducts means that the tensored inclusions $c^{\otimes n}\otimes c^{\otimes k}\to Fc\otimes Fc$ give rise to a canonical isomorphism
$$
\label{iso}\tag{1}
\sum_{n,k\geq 0}c^{\otimes n}\otimes c^{\otimes k}\cong Fc\otimes Fc.
$$
We will now define the multiplication $\mu:Fc\otimes Fc\to Fc$. By \eqref{iso}, this amounts to define a map $\mu_{nk}:c^{\otimes n}\otimes c^{\otimes k}\to Fc$, for each $n,k\geq 0$. If $n,k\geq 1$, then $c^{\otimes n}\otimes c^{\otimes k}=c^{\otimes n+k}$ and $\mu_{nk}=i_{n+k}:c^{\otimes n+k}\to Fc$ is the inclusion in degree $n+k$. If one of $n$ or $k$ is zero (WLOG suppose $n=0$), then we define $\mu_{0k}$ to be $*\otimes c^{\otimes k}\xrightarrow{\lambda_k}c^{\otimes k}\xrightarrow{i_k} Fc$, where $\lambda_k$ is the component of the left unitor of (the monoidal structure on) $\mathsf{C}$ at $c^{\otimes k}$.
With this unit and multiplication, $Fc$ is a monoid in $\mathsf{C}$: it is associative [ref]. Unitality is expressed by the commutativity of the outer square in the following diagram:
(Here, $i_{nk}:c^{\otimes n}\otimes c^{\otimes k}\to\sum_{n,k\geq 0}c^{\otimes n}\otimes c^{\otimes k}$ denotes the inclusion in degree $n,k$.) Note that, in the diagram, the arrows $\nwarrow$ and $\uparrow$ are isos by distributivity of the tensor product with respect to countable coproducts. Hence, it suffices to see that the four internal triangles commute. The top, bottom and right triangles commute basically by definition. The left triangle commutes by naturality of $\lambda$. Hence, $Fc$ is left-unital. Showing that $Fc$ is right-unital is analogous.
This finishes the definition of the action of $F$ on objects. We now define the action on morphisms. A morphism $c\to d$ in $\mathsf{C}$ induces a canonical map $Fc\to Fd$, not difficult to verify to be a morphism in $\operatorname{Mon}(\mathsf{C})$.
Let $m$ be a monoid in $\mathsf{C}$. It is left to see that the natural map
\begin{align*}
\tag{2}\label{nat}
\operatorname{Mon}(\mathsf{C})(Fc,m)&\rightarrow\mathsf{C}(c,m)\\
(Fc\to m)&\mapsto(c\to Fc\to m)
\end{align*}
is a bijection. We first see it is onto: a morphism $c\to m$ induces a morphism $c^{\otimes n}\to m^{\otimes n}$. Post-composing with the $n$-ary multiplication $m^{\otimes n}\to m$ (defined up to unique natural isomorphism, see Mac Lane's book, VII.3, Proposition 1) and summing everything up gives a map $Fc\to m$. One may verify that this constitutes a morphism of monoids.
To see injectivity, given a morphism of monoids $Fc\to m$, it suffices to see that for $n\geq 1$, the map $c^{\otimes n}\to Fc\to m$, is completely determined by $c\to Fc\to m$. The diagram
$$
\require{AMScd}
\begin{CD}
(Fc)^{\otimes n}@>>> Fc\\
@VVV@VVV\\
m^{\otimes n}@>>> m
\end{CD}
$$
commutes by hypothesis. Precomposing the diagram with the canonical map $j:c^{\otimes n}\to (Fc)^{\otimes n}$ (equal to the composite $c^{\otimes n}\to\sum_{k_1,\dots,k_n\geq 0}c^{\otimes k_1+\cdots +k_n}\cong(Fc)^{\otimes n}$, where the latter is canonical and the former is the inclusion in degree $(k_1,\dots,k_n)=(1,\dots,1)$) gives the desired result.
You can view arbitrarily-nested lists as representing an ordered tree. This is also known as a rose tree (though that term appears to be used in several contexts). The ordered tree construction forms a monad, where the unit is given by the singleton tree, and the multiplication is given by interpreting "ordered trees whose leaves are ordered trees" simply as ordered trees. Algebraically, the list monad is given by the free monoid construction, while the ordered tree monad is given by the free (nonsymmetric) operad construction. There is a monad morphism from the ordered tree monad to the list monad, given by flattening the ordered tree: this is the flattening construction you describe.
As you suspect, the free monad on the list functor is the ordered tree monad (e.g. as mentioned in these slides).
Best Answer
There's a general description of graded objects, but for the purposes of just defining graded monoids it's possible to simplify:
As a simple example, the monoid $\mathbb{N}^k$ is graded by $\mathbb{N}$ with the grading given by taking the sum of the components. Taking the monoid ring of this example produces the familiar grading of multivariate polynomials by total degree, although we need a somewhat different definition of what a grading of a ring is.
I don't quite know what "heterogeneous lists" means, but I can make a guess. Suppose you have a collection of types $T_i, i \in I$ indexed by a set $I$. Then you can construct the monoid of lists of elements where each element can be in any of the types $T_i$; equivalently, the monoid of lists of elements of the sum type $\coprod_i T_i$. This monoid admits a grading, which remember is just a homomorphism, by the monoid of lists of elements of $I$; this homomorphism is determined by sending each element to its type.
For example, suppose we have two types,
strings andints. A heterogenous list ofstrings andints looks likeand the corresponding list of types is