You won't be able to random queue with a high level, however you still have a few options

IMO, just roll the 4 until your high enough to run with your paladin. I've been working on 4 new DKs, and you'll find rather quickly that DKs are simply very OP until close to 80. I went from 59-64 last night and dual-spec'd one as blood to tank. Random queues are nearly instant since all you need to fill is the healer, and after running 6-7 instances last night, every healer loved it and most wanted to run another one. The healers were not even close to being pressed for mana.

Unless you're planning on keeping the druid long term and want to level him as well, I wouldn't take the time to set up macros and healing for him as the LFD is very fast. Also, you'll have next to no downtime as you can be pulling the next set of adds with next to no worry while your healer drinks and loots everything.

Another option is to queue with your druid, have him leave the group and invite your 84. However, your druid won't level with the team, so that can only be done a limited number of times.

The last option is to random queue and vote kick the healer and put your 84 in.