Hello. Did this trip some few yrs ago, not sure if you can rent bikes in the area, Billund is a small place but then Denmark is full of bikes..
You land on a small airport on a bi field, easy to go to "town" on bikes, not far. Flat area, not many gears needed..
What about buying some folders for the kids? Can be used for years (they do not outgrow them), and can also be used by adults later. Sounds strange to me kids not riding bikes though..
Some hotels in the nearest "town" becouse of Legoland, but not sure if they rent out bikes, especially if you are not staying in the hotel. Can remember a bikeshop, but do not know if they rent out bikes.
Folders you can manage to send as normal lugage, no extra charge for bikes unless the weight is to much.
Try to visit the "folding" forum.