Constrained Smallest Enclosing Ball Problem
I guess one simple approach would be to use any known Smallest Ball algorithm to determine the center of the optimal ball. Then you use kNN-queries to find the closest neighbour, which is likely the required point. 
However, you would need to show that the closest neighbour really is necessarily the best point. Maybe you need to actually check a number of candidates within a to-be-determined distance of the virtual center point.

Also, for a practical solution, I wouldn't use a kd-tree. R-Tree (or R*tree/R+tree/X-tree) behave better, so does the PH-Tree (a kind of quadtree).