Are there darlingtons more powerful than the ULN2803A?
Personally, I'd just use discrete MOSFETs plus flyback diodes (eg. IRLZ44N + 1N4004), but you can get 5 of them in one package (SLA5085 from Sanken) with logic-level (4V) drive: 



Don't forget the diodes across the solenoids, whichever way you choose to go. 

Darlingtons are not great for switching high current at low voltage as they drop a lot
of voltage causing a lot of power dissipation, which is part of the reason why they're very seldom seen these days in such applications. If you insist on Darlingtons there's always the TIP131 single power darlington from 40 years ago. Again, you need the diode across the load.