You should say "Ottoman war machine" and "Byzantine city of Constantinople".
Ottoman, although derived from a name, is one of the words that people like to say is "used as an adjective". The phrase "Ottoman Empire" is actually an example of this usage. (The Oxford English Dictionary lists Ottoman as an actual adjective; some people might say it is actually an attributive noun, but it doesn't make a difference to the usage in this context. "Ottoman's" is never correct when referring to something associated with the empire.)
Byzantine is definitely an adjective. It has the adjective suffix -ine; it's derived from the place name Byzantium. "Byzantine's" is wrong when referring to something associated with the empire. "Byzantinian" is also, as far as I can tell, wrong: while I see that it is used in some places on the internet, I see no reason to think it is not just a mistake. (Amusingly, someone made a post on the "Mandela Effect" reddit about this.)
The forms "Ottomans' war machine" and "Byzantines’ city" that tchrist edited to add to the question are more acceptable from a grammatical standpoint than "Ottoman's war machine" and "Byzantines' city" (they are simply synonymous to "the war machine of the Ottomans" and "the city of the Byzantines"), but they are uncommon in actual text and usually unnecessary.
(Off the top of my head, I can't think of any situation where they would be necessary, or even preferable, although I expect it would be possible to create some contrived example.)
In general, when something is called "the X Empire/empire", that's a strong clue that "X" is either an adjective, or a word that can be "used as an adjective", so you should default to using that word in attributive contexts. E.g. the Roman Empire, British Empire, French Empire, Turkish Empire, Russian Empire (see this Google Ngram Viewer chart for more).
E.g. I just invented the name "Flumflu empire"; the default assumption would be that the word "Flumflu" acts as an adjective and we can say things like "Flumflu culture," "the largest Flumflu city", "the Flumflu army".