"I like your newspaper."
Translation:Deine Zeitung mag ich.
the word order seems a bit unnatural to me. Could Ich mag Deine Zeitung also work? Seems to flow a bit easier to an English speaker.
That's correct, too. Syntax can either be subject, verb, object or object, verb, subject. Depending on the context, one might be prefered over the other. Without context, they should both be fine.
Du and Deine are mostly used in lower-case. Using them with capital letters when not the first words of a new sentence is pretty out-dated, but was and sometimes still is used for a more polite or formal 'you' while still being more casual and personal than the actual Sie formal you.
If the word is masculine/neuter AND singular, then yes. So der Hund - dein Hund, das Bier - dein Bier, but die Frau - deine Frau, die Hunde - deine Hunde
It's the same rules as choosing Ein or Eine.
Why do you have to write it backwards sometimes? It seems perfectly logical to just say Ich mag deine Zeitung to me.
It's a matter of nuanced emphasis. It's hard to describe the subtleties, but say a friend presents you an option of a magazine, book, or newspaper. "Deine Zeitung mag ich" would stress emphasis on the newspaper over other things, in this case the book or magazine options.