Your understanding of $(0+1)^*$ and $(0+1)(0+1)^*$ is correct.
$(0+1)0^*1^*$ is different from both. The regular expression $0^*1^*$ matches any string of the form $0^m1^n$, where $m,n\ge 0$. Thus, it matches every string that does not have a $1$ before a $0$. $(0+1)0^*1^*$ then matches any string that has at least one character, which may be $0$ or $1$, and after that does not have a $1$ that is followed by a $0$.
$(0^*1^*)^*$ is equivalent to $(0+1)^*$: it matches the empty string and any string of the form $$0^{m_1}1^{n_1}0^{m_2}1^{n_2}\ldots0^{m_r}1^{n_r}\;,$$ where the numbers $m_1,\ldots,m_r$ and $n_1,\ldots,n_r$ are non-negative integers, and it’s not hard to see that that covers every possible string of $0$s and $1$s. Thus, $(0+1)(0^*1^*)^*$ is equivalent to $(0+1)(0+1)^*$.
The following classes of languages seem relevant to your question.
Context-free languages.
There is a very nice characterization of context-free languages (credited to Wechler) involving concatenation product and left quotients in [1]. More details can be found in this answer.
[1] J. Berstel and L. Boasson, Towards an algebraic theory of
context-free languages, Fundam. Inform. 25(3): 217-239 (1996)
Rudimentary languages.
The class of rudimentary languages can be defined in various ways. I just mention here two equivalent possible definitions.
If $\mathcal{L}$ is a class of languages, let $\text{NLin}(\mathcal{L})$ denote the class of languages accepted by some nondeterministic Turing machine in linear time, with an oracle set in $\mathcal{L}$.
Let $\mathcal{L}_0 = \{ \emptyset \}$ be the trivial class of languages and for all $n \geqslant 0$, let $\mathcal{L}_{n+1} = \text{NLin}(\mathcal{L}_n)$. A language is rudimentary if it belongs to the union of the classes $\mathcal{L}_n$ for $n \geqslant 0$.
The following nice characterization is due to Wrathall [2].
Rudimentary languages form the smallest class of languages containing
the linear language $\{0^n 1^n \mid n \geq 0\}$ and the regular sets
and closed under the Boolean operations, inverses of morphisms and
length-preserving morphisms.
[2] C. Wrathall, Rudimentary predicates and relative computation, SIAM J. Comput. 7,2 (1978), 194--209.
Best Answer
I will use verifier based definition of NP and coNP (not that with NTM).
Given a word $w$ and a language $L$ consider a graph on $\{1,2,\dots,|w|+1\}$ where $(i,j)$ is an edge iff $w_{i\dots j-1}\in L$. Then, $w\in L^{\ast}$ iff there is a path from $1$ to $|w|+1$.
Is a complexity class closed under Kleene star?
For P the situation is easy; the machine can compute the graph and perform DFS.
For NP, the machine may guess $O(n^2)$ certificates, compute the graph and accept if there is a path. Every edge in the graph corresponds to an infix in the language. If you guess wrongly, you will incorrectly reject, but here the guesses are directed to accept if possible.
For coNP, the machine may also guess $O(n^2)$ certificates, compute the graph and reject if there is a path. Every edge in the graph also corresponds to an infix. If you guess wrongly, you will incorrectly accept, but here the guesses are directed to reject if possible.
Edit to clarify.
If the task was to show NP is closed under Kleene star, you could write ($L \in NP$):
And this is enough to show that $L^{\ast} \in NP$, since you can guess both the partition and certificates.
However, if you try to pull the same trick with $coNP$, you will get: ($L \in coNP$):
this is bad, because you've got both existential and universal quantification, so $L^{\ast}$ is not in the form required for coNP.
The idea is to guess certificates for all $n^2$ infixes of the word at once. Some of them will not be valid, but we won't use them.
If $L \in NP$ you can write:
and check existence of partition using the graph.
Given the $n^2$ certificates, the property "there exists a partition $x=x_1 x_2 \dots x_n$, such that..." is testable in polynomial time; you do not need to guess the partition.
For $L \in coNP$ you can pull the same trick now:
and since "the exists a partition..." is testable in polynomial time, it shows that $L^{\ast}$ is in $coNP$.
Edit: Another way to think about it.
You've got a word $w$ and want to show that it is not in $K^{\ast}$, where membership in $K$ can be quickly falsified. To do it, you falsify membership of as many infixes of $w$ as you can. If there is no way the remaining infixes could be joined to get the whole $w$, surely $w \notin K^{\ast}$. On the other hand, if you supplied as many falsifications as possible and there is still a way to break $w$ to $w = w_1 w_2 \dots w_n$ where you cannot falsify membership of any $w_i$, then $w \in K^{\ast}$.
Formal proof.
Suppose $K$ is a $\mathsf{coNP}$ language. This means
$x \in K$ iff $\forall y. P(x,y)$
where $y$ is polynomial with respect to $x$ and $P$ is a polynomial time predicate.
I will show that $K^{\ast} \in \mathsf{coNP}$. So I will define a predicate $R$ such that
$x \in K^{\ast}$ iff $\forall y. R(x,y)$
Here is code of $R$. "Accept" means that $R(x,y)=true$ (in this case $y$ is useless) and "reject" means $R(x,y)=false$ (in this case $y$ certifies that $x \notin K^{\ast}$)
def R(x,y):
Clearly $R$ is polynomial time computable.
If $x \in K^{\ast}$ then $x=x_1 \dots x_m$, where $x_i \in K$, so $P(x_i,z)$ is always true. In this case there is a path in the graph for any $y$, so $\forall y. R(x,y)$.
If $x \notin K^{\ast}$ then for any $(i,j)$ such that $x[i,j] \notin K$ we define $c_{ij}$ such that $\neg P(x[i,j], c_{ij})$, and $c_{ij}=\epsilon$ otherwise. Let $y$ be a suitable concatenation of $c_{ij}$.
I claim for such defined $y$ the graph has no path from 1 to n+1, and the algorithm rightfully rejects. Namely, such path would give rise to a partition $x = x_1 x_2 \dots x_n$. However, since $x \notin K^{\ast}$, there exists $i$ such that $x_i \notin K$. Suppose $x_i = x[k,l]$. But in this case we supplied $c_{kl}$ such that this edge should not be present in the graph.