They don’t mean precisely the same thing either. “Back o’ Bourke” and “beyond the black stump” refer to remote locations generally. They’re more like a alterntive for “The middle of nowhere”. The examples in the OP refer to a specific remote city/town. To highlight the difference, you’d commonly refer to a town being beyond the black stump, but you’d never refer to a town as being in “Nowheresville”.
The connotation I’ve always understood for “Timbuktu” (or Tambouctou as it’s often written these days) is not so much “someplace in the middle of nowhere” but rather “a generic far-away remote alien city” with a dollop of 1001 Arabian Nights exotic mystique thrown in for good measure.
(In fact, I got the vague impression that one of the Arabian Nights stories, “The City of Brass”, might actually be set in Timbuktu, although I don’t think it actually says that in the story. Just some place far to the west (west of Arabia, that is).)
If you just want to imply someplace far away in Norwegian, you can say Langtvekkistan, literally Far-away-istan, which was popularized and possibly invented by writers for the Norwegian version of the Donald Duck comic books.
If instead you want to describe a place that’s isolated and backwards and where the people are just a bit inbred and suspicious of outsiders, you’d go with Indre Enfold, a play on the actual counties of Østfold and Vestfold and the Norwegian word enfoldig, meaning simple in the sense of “a bit slow”. Indre means inner - Outer Enfold is presumably along the coast and therefore has at least some contact with civilization, while Inner Enfold is an isolated mountain valley where strangers rarely go.
I was going to say, “Timbuctoo” conjures up images of somewhere remote but exotic.
The most common synonym for “Middle of nowhere” that I’ve heard around here is “Woop Woop”, which (IMHO) carries connotations of “nothing there except the pub and one of those tin windmills that draws water”. “Out bush” is another one but tends to imply the subject is actually doing something (eg work, hunting, fishing, camping etc) as opposed to simply being in the middle of nowhere, if that makes sense.
I’ve also heard people refer to “Bumfuck” (sometimes with Upper/Lower/one of the compass points as a prefix), “Nowheresville” and “The Fukawi” (as in “The fuck are we?”). Never heard of “Bumfuck, Egypt” though.
“Podunk” doesn’t necessarily refer to a particularly remote or exotic place, but rather, to a completely boring and generic small town where nothing interesting happens. You probably could drive from Podunk to the big city in a day, except that nobody actually does.