The description says: "Kill an opponent's King or Queen character". I guess I have to do it myself with things like Valar. If my opponent kills a queen for the claim of the military challenge or with his own Valar this would not be sufficient for the achievement.

Why is that? The character is still being killed as a result of your challenge. It doesn't matter if they made the choice who died...you killed it.