The question illustrates  three separate German verbs that are easily confusable, and have closely related meanings: the two phrasal verbs *herumspazieren* and *spazieren gehen*, and the simple verb *spazieren*.

 - According to _Duden_ [*herumspazieren*][1] is colloquial, and means 'to amble here and there without a clear aim' ("hierhin und dorthin spazieren"). 
 - [*Spazieren gehen*][2] is not considered to be colloquial, and simply means 'to go for a walk' ("einen Spaziergang machen"). 
 - For [*spazieren*][3], _Duden_ distinguishes two meanings. The first is basically synonymous to _herumspazieren_ ("gemächlich [ohne bestimmtes Ziel] gehen; schlendern"), the second one is a synonym of _spazieren gehen_. The latter meaning is marked as outdated ("veraltend").

Note that the degree to which they are interchangable is very gradual. I suspect that speakers will generally find _ich gehe mit meinem Vater spazieren_ fully acceptable, but fewer may like _ich spaziere mit meinem Vater herum_, and _ich spaziere mit meinem Vater_ may be rejected by quite a few. Yet, if you add an adverbial, I think their acceptability is greatly improved:

> _Ich gehe mit meinem Vater im Park spazieren._
>
> _Ich spaziere mit meinem Vater im Park herum._
>
> _Ich spaziere mit meinem Vater im Park._

At least to me, all three are fully acceptable. If pressed to define the meaning difference between them, I'd agree that the first is more directed (perhaps even following a marked route), whereas the other two have a much more spontaneous ring to them.

As to the regional differences, I think that the simple verb _spazieren_ may be more frequent in southern varieties of German, whereas northern German varieties may have a preference for the phrasal variants. 

Some support for this hypothesis comes from Google queries: Out of the ~39400 hits for the query string [`"spazierte *" site:at`][4], ~3250 hits also match the query string [`"spazierte * herum"` site:at][5]. This means that less than every tenth occurrence of _spazierte_ (about 8 percent) is followed by _herum_ if the search is restricted to websites that are associated with the Austrian `.at` top-level domain. 

If the same searches are conducted for the `.de` top-level domain, which is associated with Germany, the proportion is very different: out of the ~167000 hits for [`"spazierte *" site:de`][6], ~67200 also match [`"spazierte * herum" site:de`][7], i.e. about 38 percent. In other words, the probability that _spazierte_ occurs together with a following _herum_ is more than four times as high for `.de` domains than for `.at` domains.

[1]: https://www.duden.de/rechtschreibung/herumspazieren
[2]: https://www.duden.de/rechtschreibung/spazieren_gehen
[3]: https://www.duden.de/rechtschreibung/spazieren
[4]: https://www.google.de/search?q="spazierte+*"+site%3Aat
[5]: https://www.google.de/search?q="spazierte+*+herum"+site%3Aat
[6]: https://www.google.de/search?q="spazierte+*"+site%3Ade
[7]: https://www.google.de/search?q="spazierte+*+herum"+site%3Ade