"I take a walk at the park with her."
を can be used to mark route, like part of your path.
こうえん を さんぽする walk through/past the park (start elsewhere, walk through the park, end elsewhere)
こうえん に さんぽする walk to the park (start elsewhere, end at the park)
こうえん で さんぽする walk at/in the park (start & end at the park, no where else in between)
Extra example: はし を わたる cross the bridge
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.