I also wonder if some of these are actually false cognates, or if there is a much earlier common origin with false associations that came afterwards

Common but old origin tends to make words diverge over time. Compare for example:

Old languages	Modern languages
Proto-Germanic */fimf/	English ⟨five⟩ /'fa͡ɪv/
Latin ⟨quinque⟩ /'kʷin.kʷe/	Italian ⟨cinque⟩ /'t͡ʃin.kʷe/
Proto-Celtic */'kʷen.kʷe/	Irish ⟨cúig⟩ /'ku:ɟ/
Sanskrit ⟨पञ्चन्⟩ /'pɐɲ.t͡ɕɐn/	Hindi ⟨पाँच⟩ /'pɑ̃:t͡ʃ/

All those eight are true cognates, they’re all from Proto-Indo-European *pénkʷe. But if you look only at the modern stuff, those four look nothing like each other - and yet their [near-]ancestors (the other four) resemble each other a bit better, Latin and Proto-Celtic for example used almost the same word.

They also get even more similar if you know a few common sound changes, like:

• Proto-Italic (Latin’s ancestor) changed PIE *p into /kʷ/ if there was another /kʷ/ nearby
• Proto-Germanic changed PIE *p into *f (Grimm’s Law)

In the meantime, false cognates - like the ones mentioned by the OP - are often similar now, but once you dig into their past they look less and less like each other, the opposite of the above.

They also often rely on affixes that we know to be unrelated. For example, let’s dig a bit into the first pair, desert/deshret:

• Latin ⟨deserō⟩ “I desert, I abandon [unseeded], I part away” - that de- is always found in verbs with movement from something, or undoing something. It’s roughly like English “away” in trennbare phrasal verbs like ⟨part away⟩, ⟨explain away⟩, ⟨go away⟩
• Egyptian ⟨dšrt⟩* “the red” - the ending -t is a feminine ending, like Spanish -a. And the word isn’t even ⟨deshret⟩ in Egyptian, it’s more like /ˈtʼaʃɾat/

Suddenly our comparison isn’t even between ⟨desert⟩ and ⟨deshret⟩, but rather between /seɾo:/ and /ˈtʼaʃɾa/. They… don’t look similar at all.

* see here for the word in hieroglyphs.

Other bits of info:

• ⟨shark⟩ - potentially a borrowing from German ⟨Schurke⟩ scoundrel. Think on loan sharks, for example, those people who chase you over and over; apply the same meaning to a fish and you got a predator, a shark fish. Note that the old name of the fish (dogfish) also hints the same behaviour.
• Turkish ⟨kayık⟩ - the word is attested as ⟨qayğıq⟩ in Khaqani Turkic. I might be wrong but I think that the -yık (Old Turkic “guk”) forms adjectives, as the Azeri cognates that I’ve found using this suffix are mostly adjectives; see qıyıq, ayıq, sayıq. Kind of tempting to interpret it etymologically as something like “sliding boat”, with the “boat” part being eventually omitted.