When it comes to calories burned, total distance covered is the major factor. Speed is largely irrelevant.
However, walking faster does get your heart rate higher, and creates additional fitness benefits.
But the impact of running is hard on the body, and it is generally recommended to build up a solid walking base before transitioning to running. 2-3 months of walking, and being able to comfortably walk 3 miles briskly are good benchmarks of this. And when you do want to start running, the interval approach is a good one. A Couch to 5K plan is a good way to get towards running www.sparkpeople.com/resource/fitness_artic
One alternative way of increasing the intensity of your walking is to include some hills on your route.