Sometimes when we were going to be out for several hours we would give our dogs frozen Kongs and they loved them. Yes they do make a mess so it's probably best to let them have it on a kitchen floor or a crate.
It's also a good way of feeding your dog. Instead of putting it in a bowl, stuff the food in a Kong. If you do that, rather than getting fat on extra treats, they are just working harder for their dinner.
You can stuff with kibble or, as we feed raw, mince and veg.