I grow up next to an old medieval town. I'm not a stranger to how these towns are build. There are a lot of places where you can plant trees in the streets. Of course, the streets will be narrower with the place for just the pedestrians, bikes, and emergencies services. It's a fully car free town in this case. Your link is perfect. You have Pl. de España on the right where you could plant a small forest on it.
You see all the terrasses. They could have trees in the middle.
For this purpose of reducing the temperature, you have this project where they will keep a central bus stop but plant many trees to cover it.