You haven't said precisely what you mean by an algorithm here, and this is actually a nontrivial issue since your question is outside the usual finitary context of computability theory, so it isn't clear what you might mean, and there are choices to be made about it.
One way to make the concept precise would be to work with $\mathbb{Q}^n$ rather than $\mathbb{R}^n$ (or some other countable dense set), that is, to finitize the problem by regarding all the relevant reals as rational. In this case, we can use a standard Turing machine concept of computability to make the question precise. For this manner of formalization, we regard the "input" as fixing the oracles for the $K_i$, and the question is whether there is a Turing machine program that can detect the answer correctly regardless of the oracle (subject to them satisfying your hypotheses). Let me assume first that the hypotheses are that exactly one of the $K_i$ are non-convex.
Theorem. With the $\mathbb{Q}^n$ formalization just described, the answer is yes, there is an algorithm.
Proof. Consider the algorithm that systematically produces all triples $(p,q,r)$ of rational points in $\mathbb{Q}^n$, such that $q$ is on the line from $p$ to $r$, and checks membership in each $K_i$. Note that any instance of non-convexity will therefore be revealed. Thus, we will at some finite time in the algorithm, discover which of the $K_i$ is not convex, and thus produce the correct answer in finitely many steps. QED
The previous algorithm relied on the fact that instances of non-convexity can be discovered in finitely many steps.
Theorem. In the $\mathbb{Q}^n$ formalization, in the context where the input sets $K_1$ and $K_2$ might both be convex (and in such a case only, we allow the boundary to be a hyperplane), then there is no computable procedure that will always work.
Proof. Suppose that there were such a procedure in the case $n=1$. Let $K_0=(0,2)$, $K_1=(0,1)$ and $K_2=[1,2)$. The algorithm will halt in finitely many steps, having made queries about reals $q_0$, $q_1$, ... $q_n$, and stating that one of the sets, lets suppose $K_1$, is convex, which is true. Consider now the modification of the sets by letting $r$ be the largest $q_i$ below $2$ (or $\frac32$, whichever is larger), and using $K_1'=(0,1)\cup (r,2)$ and $K_2'=[1,r]$. Since the answers to the queries about the $q_i$ are exactly the same for this configuration as in the original problem, the algorithm will again say that $K_1'$ is convex, but in this case, it would be incorrect. QED
Since the $K_i$ input is infinitary in nature, it isn't immediately clear what you might mean by "complexity class". However, the problem does have an inherent semi-decidable nature, since instances of non-convexity are revealed by a single instance. In the case where one side or the other must be non-convex, this semi-decidable nature becomes decidable, since we can know which is convex by discovering the other set to be non-convex.
Let us now try to consider the general case of $\mathbb{R}^n$. We don't have a standard formal notion of computability here (there are several distinct notions of computability on the reals, such as BSS machines, computable analysis, descriptive set-theoretic notions of "computability", infinite time computability). Note that the input to the algorithm is the sets $K_i$, rather than a real number.
But let's try to be flexible and allow a more generous concept of algorithm, subject to the following properties: an algorithm is a deterministic procedure that (somehow) produces points $p$ in $\mathbb{R}^n$, makes inquiries about whether they are in $K_0$, $K_1$ and $K_2$, and then uses the resulting yes/no answers to those queries to produce additional real numbers about which queries may be made. Eventually, based on the result of the queries, the algorithm is supposed to give an output by specifying whether $K_1$ or $K_2$ is convex. In particular, in this set-up, the same algorithm can be used with many different $K_0$, $K_1$ and $K_2$, and the reals produced depend only on the answers to the queries, rather than on the oracle sets themselves. We give the "input" of $K_i$ to the algorithm by attaching the black boxes, without providing any additional information about the $K_i$ sets, except that they satisfy the assumptions you identified. In this case, it doesn't matter whether one insist that exactly one or at most one $K_i$ is non-convex.
Theorem. With the $\mathbb{R}^n$ manner of formalization just described, there can be no algorithm correctly identifying a convex $K_i$.
Proof. Suppose that there were such an algorithm in the case $n=1$. Call the algorithm $e$. Consider the set $Q$ of all real numbers that will ever be produced by the algorithm $e$ for a membership query for any combination of sets $K_0$, $K_1$ and $K_2$. Our assumptions on the nature of the algorithm ensure that $Q$ is a countable set, since any real produced during the course of any computation is produced as the result of a finite sequence of yes/no answers to the previous queries, and there are only countably many such possible patterns of membership. Let $r\lt s\lt t$ be real numbers not in $Q$, and consider the two possible inquiries:
- $K_0=[r,t]$, $K_1=\{r\}\cup[s,t]$, $K_2=(r,s)$.
- $K_0=[r,t]$, $K_1=[s,t)$, $K_2=[r,s)\cup\{t\}$.
Because these two input configurations agree on $Q$, the algorithm must give the same output for both of them. But in the first case, it $K_2$ that is convex, while in the second, it is $K_1$ that is convex. So there can be no such algorithm. QED
