Complement means relative complement $Σ^* - L$. You already have closure under set subtraction and, in fact, also intersection and even interleave. So, the real question is how to do set-subtraction.
You can evaluate it algebraically, but you get a system that amounts to the description of a deterministic automaton. I will only illustrate it with a couple of examples, one of which will involve the relative complement with respect to $Σ^*$, where $Σ = \{a,b\}$.
Example 1: $a b^* a - (ab)^*a$:
Set $A = a b^* a - (ab)^*a$. Using the identity $x^*y = y + x x^* y$, we write
$$A = a b^* a - (a + a b (a b)^* a) = a\left(b^* a - 1 - b (a b)^* a\right) = a B,$$
where $B = b^* a - 1 - b (a b)^* a$ and $1$ denotes the empty word.
The set-theoretic subtraction of $1$ is trivial since $b^* a$ does not contain the empty word. Therefore, we can write $B = b^*a - b (a b)^* a$. Thus, continuing on, we have
$$B = a + b b^* a - b (a b)^* a = a + b\left(b^* a - (a b)^* a\right) = a C + b D,$$
where, $C = 1$ and $D = b^* a - (a b)^* a$.
For $D$, we have
$$D = a + b b^* a - a - a b (a b)^* a = a\left(1 - 1 - b (a b)^* a\right) + b b^* a = b b^* a,$$
since the set-theoretic identity holds $x - x - y = 0 - y = 0$.
The resulting system
$$A ≥ a B, B ≥ a C + b D, C ≥ 1, D ≥ b b^* a,$$
has to be written as a system of inequalities to avoid infinite regresses that occur if repeats of terms appear on the right-hand side (e.g. an equation like $D = ⋯ + D + ⋯$); and it is the least solution we seek out.
Solving for $(C,D)$ immediately yield the results $(C,D) = \left(1, b b^* a\right)$. Substituting into the other two inequalities yields
$$A ≥ a B, B ≥ a + b b b^* a = \left(1 + b b b^*\right) a,$$
whose least solution is
$$(A,B) = \left(a \left(1 + b b b^*\right) a, \left(1 + b b b^*\right) a\right).$$
The corresponding automaton has states $A$, $B$, $C$, $D$, plus whatever other states result from reducing the expression for $D$ to a system of inequalities. The start state is $A$, and $C$ is a final state, plus whatever other final state might come from the subsystem headed by $D$. (There are none. The subsystem headed by $D$ leads back to $C$ as its sole final state.) The expression of interest is that for $A$, and we can thus write
$$ab^*a - (ab)^*a = a\left(1 + b b b^*\right)a.$$
Example 2: $(a + b)^* - (a + b)^* b b (a + b)^*$
Setting this expression to $A$, you can write
$$A = 1 + a A + b \left(A - b (a + b)^*\right) = 1 + a A + b B,$$
where $B = A - b (a + b)^*$. In-line substituting this expression for $A$ into $B$ yields
$$B = 1 + a A + b \left(B - (a + b)^*\right) = 1 + a A.$$
The last equality follows from the identity $f(a,b) - (a + b)^* = 0$, for any regular expression $f(a,b)$ in $a$ and $b$, since the set corresponding to $(a + b)^*$ is maximal. Thus, the corresponding system is
$$A ≥ 1 + a A + b B, B ≥ 1 + a A,$$
which, upon in-line substitution of the expression for $B$ into $A$, yields
$$A ≥ 1 + a A + b + b a A = 1 + b + (a + b a) A,$$
whose least solution is $A = (a + b a)^* (1 + b)$. Thus,
$$(a + b)^* - (a + b)^* b b (a + b)^* = (a + b a)^* (1 + b).$$
