I would definitely use as many towels as possible, as per @Peter Crotty's answer - but I wouldn't wet them. Water is a much better conductor than air. Wrapping them with as much material as possible is the key, preferably light coloured on the outside to reflect as much light/heat as possible.
We tend to think that insulating things makes them warm but it helps to think of it as keeping them the same.
A suggestion: you could take 2 towels, fold the darkest one into 2 or 3 and wrap the goodies, then drop that bundle into the centre of the lighter towel, gather the corners into a "bag" that you can hold with one hand. As you walk, keep the "bag" in the shade of your body as best you can - but try to stop it contacting your body because, at 37 degrees, you are probably the worst enemy. The bag will mean you can hold the payload without the need to hug it to your chest.
EDIT: Another important thing I've just thought of.... You don't want the towels to be warm before you wrap the ice creams in them. If they are warm at the start (likely) then you need to allow them to cool in the air as you walk to the shop - but without letting the sun warm them! You'll have to figure that out for yourself. If they are not too warm then wrap the darker one in the lighter one to keep it the coolest.