Inversion is the reversal of the normal word order in a sentence or phrase. There are two types of inversion:
Subject-verb inversion, where the subject and the main verb switch positions and the word order becomes verb + subject:
On the top of the hill stood an old oak tree.
Subject-auxiliary inversion, where the subject and the auxiliary switch positions and the word order becomes auxiliary + subject (+ verb):
Hardly had I arrived home when my phone rang.
Source: http://www.grammaring.com/what-is-inversion
You seem to be asking about subject-auxiliary inversion, which here depends on the use and importance of 'only'.
The way 'only' is used in your second sentence does indeed make it a case for subject-auxiliary inversion. Here 'only' is used together with 'when', and implies conditionality: the 'subject-first' form of this sentence would be
The settlers stood much of a chance only when Mohegan scouts led them through the woods.
The first part of the sentence is dependent on the second through "only when" -- for the settlers to stand much of a chance (1st part) it was necessary (signified by the use of 'only when') that the scouts lead them through the woods (second part of the sentence.)
'Only' is integral to this sentence and you cannot rewrite the sentence omitting 'only.' Therefore when rewriting this sentence to begin with 'only', subject-auxiliary inversion must be applied and the auxiliary 'did' needs to be introduced:
Only when Mohegan scouts led them through the woods did the settlers stand much of a chance.
This is a typical example of subject-auxiliary inversion.
HOWEVER, the use of 'only' is very different in your first sentence:
Only a few years ago the herring gull more often than not remained close to the sea and nested on cliffs.
The herring gull more often than not remained close to the sea and nested on cliffs... (when?) ...only a few years ago.
'Only' is not applied to the subject (herring gull) here but merely to 'a few years ago', so as to emphasise that it was only a short period of time in the past. 'Only' does not impose any conditionality or dependency between 'the habits of the nesting gull' and 'a few years ago' -- moreover 'only' is not indispensable to this sentence: you can omit it, rewriting the sentence as "a few years ago, the herring gull more often than not remained close to the sea and nested on cliffs." So this sentence is not a case for subject-auxiliary inversion.
In short, subject-auxiliary inversion is applied to your second sentence but not to your first because (the use and significance of 'only' being very different in both sentences) only the second sentence is a suitable case for applying subject-auxiliary inversion.
NOW CONSIDER THIS SLIGHT (invented) VARIATION:
The herring gull began to remain close to the sea and nest on cliffs only a few years ago.
Meaning: this is a new trend as far as the herring gull's nesting habits are concerned. When did it begin? Only a few years ago.
The herring gull only began to remain close to the sea and nest on cliffs a few years ago.
It was only a few years ago that the herring gull began to remain close to the sea and nest on cliffs.
That changes the whole sense and significance of 'only' because 'only' now creates a conditional link between 'the nesting habits of the herring gull' and 'a few years ago.' Only has now become integral to the sentence because you cannot omit 'only' without changing the meaning of the sentence. Therefore this sentence has now become a case for subject-auxiliary inversion and when rewriting it to begin with 'only', the auxiliary 'did' must be added:
Only a few years ago did the herring gull begin to remain close to the sea and nest on cliffs.
I acknowledge that it was the excellent answers earlier provided here by Josh and John Lawler which helped me to better understand the conditions for applying subject-auxiliary inversion, and allowed me to re-edit this into a more coherent answer.