Let $K_0$ be the unit disk in $\mathbb{R}^2$. $K_1$ consists of the point at $(1,0)$ and some other point $\zeta$ uniformly and randomly chosen on the boundary of $K_0$ (the unit circle). It is not convex. $K_2$ is the complement of $K_1$ in $K_0$. It is convex. Therefore this is a valid instance of the problem.
Suppose you start with $x$ at $(1,0)$ any $y$ in $K_2$, say at $(0,0)$. The probability that any given algorithm ever queries $\zeta$ is $0$. Therefore, almost surely, the result of all queries will be to detect additional points in $K_2$, but never any additional points in $K_1$. One will therefore be unable to determine which of $K_1$ or $K_2$ is the convex subset.
Contemplate a similar situation in which $K_1$ is the intersection of a ball of radius $\delta$ around $(1,0)$ with $K_0$ and again $x$ is at $(1,0)$. This time, $K_1$ is convex and $K_2$ is not. Given any algorithm that purports to solve the problem and any natural number $N$, choose $\delta$ so small that the algorithm does not probe $K_1$ within $N$ steps. (If it is a stochastic algorithm, the tiny diameter of $K_1$ implies the chance of probing it will be vanishingly small). This shows the number of steps in the algorithm is unbounded (or the expected number of steps is arbitrarily large if the algorithm is stochastic). The best we can say is that the two sets can be differentiated using a number of steps proportional to a ratio of the areas.
To distinguish among the two cases, you are essentially undertaking a search for a second point in $K_1$ (which is tiny), but all your probes are always returning points in $K_2$. Evidently a completely random search (uniformly over $K_0$) is going to perform as well as anything else might. (Once you obtain $2$ points within each of $K_1$ and $K_2$, the game is almost over: it's straightforward to construct a small number of additional points that tell you which is the convex subset.)
These considerations don't rule out a solution to the problem, but they imply either that the solution must depend on additional assumed properties of $K_1$ and $K_2$; e.g., that they both have positive measure with a known nonzero lower bound, or else that a different model of space is needed; e.g., that it is totally discrete and contains a finite number of points (which is a more realistic model of what computers usually do).