First thought was "royalty" and then that it's somewhat similar to
Balthazar which I enjoy. "Villain" sneaked in after that, though, because the name is also similar to Valdemort and, just for fun, Baltar sidekicked since
Balthazar had already come up. Easy enough for me to squash down the villain association so, yes, I think
Valdemar is a handsome name. :)