The art of Counterpoint, as studied by composers for centuries, gives exact details on how to correctly ornament any melody. The lists of ornaments cited as point 4 in the question is only a subset of the possibilities given to us by counterpoint.
There are five main species of counterpoint. The treatise by Johann Joseph Fux is today the most common source for an in depth description of counterpoint. In a nutshell, species counterpoint categorizes intervals into consonant (octaves, perfect fifths and fourths, and major and minor thirds and sixths) and dissonant (seconds, sevenths, and tritones). Then, it gives guidelines for the placement of intervals based on the pattern of strong and weak beats.
Note that in all the examples of counterpoint given here (images are from wikipedia), the added melody is the top voice. These same counterpoint rules can apply to any melody that also has an accompanying harmony (as described in point 1 in the question above).
First Species: Also note against note counterpoint. Since all pitches fall on downbeats, all intervals must be consonant.
Second Species: Two notes in the counterpoint voice are set against each note in the given voice. The intervals on the downbeats should be consonant intervals, whereas the second note can be consonant or dissonant. When dissonant, the best choice is either a passing or neighbor note.
Third Species: Four notes against one. This species extends the use of dissonances in second species. The first and third notes of every four-note group should be consonant while the second and fourth may be dissonant.
Fourth Species: Here, notes in the upper voice are suspended over the bar line, often creating a dissonance on the downbeat of the bar. When dissonant, the upper voice must resolve downward to a consonant interval.
Fifth Species: This species combines the methods described in the previous four. The example shows how this species can be used to create well ornamented melodies in a free style.
Species counterpoint can at first seem very limiting, but through its practice, it can be used to create very exciting melodies and counter-melodies. Knowing how and when to use consonance vs. dissonance allows complete control over the design of a melody.