[bakaelite]

All those are grammatically fine in English.
"I went there—uh, to the store."
The pause there is fine. "I went there" is linguistically sound because of a noun and verb phrase. "To the store" is fine because it's a prepositional phrase and it follows the rule of a preposition+noun phrase. I can actually make a tree diagram of that sentence.

But an English speaker wouldn't say "Store the went, uh, I there to." It breaks linguistic patterns and the diagram would be really messy.

As for "行きました、郵便局に" notice the comma (or pause in conversation) breaks the verb and noun phrase, but the particle remains with the noun.

And yes, the assignment is basically having me look for patterns in language syntax flexibility. My Japanese is basic, because I have been studying it linguistically in tandem with other languages, and I only started "really learning" Japanese for communication last summer, when I studied in Osaka, researching Japanese educational practices.