Stench is more formal.
Stink is much more casual and not very polite; not a bad word, that is, just not very vornehm. (A child might say, Ew, it stinks in here, but in public, a parent would probably correct that to, It doesn't smell very good, or There's a bad smell in here.) Both are always strong bad smells.
Odor is also rather formal and in modern use I would say more likely to be bad than good, euphemistic for stink That is, for a good smell we would often add a positive adjective. But there may be a few collocations where it's more common. I think we might say the odor of incense in a church, for example.
One place where only scent is used is for the trail of an animal, for example, what hunting dogs or police dogs track, or what attracts other animals in mating season.
I agree that as a synonym for perfume and cologne, fragrance is the most common, but scent is also possible, though that may be somewhat dated or BE usage. For other pleasant smells either scent or fragrance is fine. But I also agree that both are probably more often used for artificially produced smells (air freshener, scented candles, incense used at home, that kind of thing).
For cooking things like gingerbread, or outdoor things like real pine trees or a wood fire, I personally would probably just say (wonderful) smell. Fragrance or scent in that kind of context sounds more literary or poetic to my ears.
Hard to say, really, without concrete examples.