If $L_0$ in a context-free language, this doesn’t guarantee that its complement is context free. For example, consider the language

$$L_0 = {a,b,c}^* setminus {a^nb^nc^n : n geq 0}.$$

This language is context-free, but is complement (with respect to ${a,b,c}$) is not.

Another way to formulate your question is as follows: given a context-free grammar for a language $L$, is there an algorithm that either constructs a context-free grammar for the complement of $L$, or determines that the complement of $L$ is not regular? Such an algorithm can be used to decide whether the complement of $L$ is context-free. However, this is undecidable, as we now show following Hendrik Jan’s notes.

Recall that given a grammar $G$ over an alphabet $Sigma$, it is undecidable whether $L(G) = Sigma^*$. Let $#$ be a new symbol, and construct a grammar for the language

$$ L = L_0 # Sigma^* cup Sigma^* # L(G), $$

where $L_0$ is a context-free language whose complement is not context-free (if $|Sigma| geq 3$, we can use the one above, and if $|Sigma| = 2$, we can encode $a,b,c$ as $a,ba,bba$; if $|Sigma| = 1$ then it is easy to check whether $L(G) = Sigma^*$). If $L(G) = Sigma^*$ then $L=Sigma^*#Sigma^*$, and so the complement of $L$ is context-free. Otherwise, suppose that $w notin L(G)$. Then

$$ overline{L} cap Sigma^* # w = (Sigma^* setminus L_0) # w, $$

which is not context-free, and so $overline{L}$ itself is not context-free (since the context-free languages are closed under intersection with a regular language). This shows that $overline{L}$ is context-free iff $L(G) = Sigma^*$.

The problem of deciding whether $L(G) = Sigma^*$ is actually not recursively enumerable. This means that there is no algorithm which, on input $G$, halts iff $L(G) = Sigma^*$ (however, there is a simple algorithm that halts iff $L(G) neq Sigma^*$, namely go over all words in $Sigma^*$ in parallel, and check whether each of them belongs to $L(G)$). Therefore there is no algorithm that, given a context-free grammar for a language $L$, halts iff the complement of $L$ is context-free.

In other words, even the following solution to your problem does not exist: an algorithm that attempts to construct a context-free grammar for the complement of the given context-free language, and either halts with the grammar, or never halts (if the complement is not context-free).