"I take a walk at the park with her."
No, you are not thinking in Japanese. Japanese words refer to different ideas and those ideas do not completely overlap European ideas. There is no word for "with" in Japanese. It is expressed using different words and phrases. と does not mean "with." ~といしょうに means "with." The trick to learning a different language is to figure out 1. that your own native language does not cover every idea or point of view and 2. what the words refer to. It's not a code.
No, As I stated above to someone else, you are thinking English, not Japanese. When you walk the dog, are you using the dog in place of your legs? I have never heard it said your way. The answer is correct as given. 散歩 does not perfectly translate into "walk." There is a difference and your challenge as a student of Japanese is to learn it as it is, not to try and bend it to your own language. If I were you, I would learn the word as a synonym, not as substitute. 散歩 implies leisure. Other synonyms: mosey, stroll, meander, etc.
By the way, in English, you may hear "I'm going to go run the trails." So this should not be a stretch.
This all-hiragana answer is a complete and utter eyesore. Please accept 「彼女と一緒に公園を散歩します。」; it is the same thing, but written properly.
Also I believe that it would also correct to use で rather than を, like so: 「公園で散歩します。」. This is what comes up on Google results more often than the currently accepted answer anyway.