The way you formulate your problem, as a black box, invites to use (as Bitwise says) combinatorial search methods. The most accurate is Branch and Bound, but you may consider suboptimal and less computationally heavy methods like the floating selection methods, which are also quite trivial to implement. The latests are basically greedy search algorithms.
As I understand, all these methods apply for your particular problem, since you are using a distance function which thus verify the monotonicity condition. This paper offers you a more up to date overview on the topic.
P.S. In forward feature selection you start with an empty feature set. Then you look for the feature out of the total set which leads the maximum KLD. And then you go on proceeding like this until you see very small or no improvement, or until you reach a given number of features.
In backward selection you proceed in the opposite direction: you start with the whole set of features, and go step by step eliminating the one whose absence worsens the maximum distance the least. The one whose removal harms the least.
That should be easy to try. For more advanced techniques, you may have a look at some packages like scikit or weka.