A warrior name describes the basic, obvious qualities of the cat. That means no history, no commemoration, and nothing that requires explanation or backstory. The name should give you an image of the cat all by itself, using straightforward terms that the clan cats would be familiar with. It should neither exalt nor degrade.

Warrior names have a prefix, given by the mother within the first few days of the cat's life, and a suffix, given by the leader after the cat completes warrior training.

Prefix = beginning part
Suffix = ending part

The prefix must be a
fur color,
body shape,
or something from the cat's natural surroundings that involves the above
(such as a plant, animal, or time with regard to sky color).

A prefix refers to appearance and appearance only. What else could you notice about a newborn?

The suffix must
state how the prefix applies (fur, tail, step),
mention a part of the cat (claw, fang, whisker) that the cat is skilled with or uses often,
or describe the cat's personality with an adjective-convertable noun (flower, storm).

Self-Explanitory

fur
pelt
stripe (for tabbies)

Feline Anatomy

Tail, belly, throat, face, leg, ear, nose, whisker, and foot are all fine suffixes. However, keep in mind that if you use one of these, the prefix should apply to the majority of the cat as well as the indicated area.

Special Attributes

claw = fierceness and skill with claws
fang = fierceness and skill with fangs
storm = rough, passionate, boisterous (stormy)
flower = ornate and feminine (flowery)
heart = affectionate, sincere, jovial (hearty)
stream = fluid movement and gracefulness
nose = curiosity
whisker = sensitivity
tail = good balance

Non-Warrior Suffixes

kit = baby cat
paw = apprentice (cat 6 months or older undergoing warrior training)
star = leader of a Clan

Leaf is not the imperative suffix for medicine cats and flower is not the imperative suffix for queens.

Keep in mind that while there are some popular words that sound cool or pretty, they don't serve a purpose as a Clan cat suffix and detract from its quality.

Cats can't sing. They can chirp, yes. This is not a song; it's a chirp. They know about bird songs, yes, but unless the cat has a vocal deformity, it can't sound like that. Because bird songs are the only songs of which Clan cats would know, and because chirping does not sound like bird song, they would not think of chirping as singing. Song does not mean happy; it means song. Songs can be sad, angry, and all sorts of moods, so song does not indicate a happy or cheery disposition.

Cats don't know about dancing. At all. They aren't made of liquid and don't like to swim, so they wouldn't have a pool. Fall suggests decline and failure, so it would be dishonorable to say the cat has a fall. Soul and spirit are too mystic - spirituality on that level is reserved for the medicine cat, but giving a medicine cat a suffix like that is redundancy. Cats' shadows are all more or less the same, so using shadow as a suffix says nothing. Cats also don't have weather or foliage.

This page advises against frost and fire as suffixes, as they're associated with colors.

Medicine cat names are no different from warrior names. If you showed someone two names, one of a warrior and one of a medicine cat, that person shouldn't be able to tell the difference. Making a cat a medicine cat instead of a warrior doesn't change anything about the requirements of the name. Using leaf as a suffix does not mean the cat is a medicine cat. It means the cat has leaves.

Mothers don't know their kits will grow up to be medicine cats. In most cases they would expect them to become warriors and as such would give them names according to this belief. It is not mandatory for a medicine cat to have a plant in their name.

Why not in the prefix?
Kits are born with their eyes closed. After they open, they're always blue for several weeks. A mother would name the kit for easy-to-recognize appearance traits like fur color or size. She wouldn't wait weeks to see what their eye color is. Eye color is less noticable than other appearance traits and something you have to be in front of the cat's face to see.

Why not in the suffix?
As explained above, the prefix must be something to do with size or color. If you take a brown tabby with green eyes and name him Dustleaf, you're saying that the cat has leaves like dust.

As for Starkit, Ten hopes she becomes leader.

In the Clans, cats refer to winter as leaf-bare, spring as new-leaf, summer as green-leaf and autumn as leaf-fall.
Thus winter, spring, summer, and autumn would not be in their vocabulary. Fall would mean a decline, not a season.
If, for some reason, they did use the human names for the seasons, they wouldn't name kits after them. Cats cannot look like seasons. They can look like snow, yes. Snow is a fine prefix. They can look like dead leaves, yes, but mothers don't name their kits after dead things.

It only works if the cat steps like the prefix. Whitestep does not mean the cat has white paws. Whitestep means the cat steps whitely, which doesn't work. If you want to show white paws, use the name Whitefoot. However, the cat must have a majority of white fur in order to have been named Whitekit.

The step suffix works with most animal prefixes (Shrew, Crow) and some adjective prefixes (Big, Small).

Names such as Ravenfeather can work because the cat is the color of a raven feather. However, this page advises against this practice because it leads to names like Cedarbark and Stormcloud.
When you use cedar as a prefix, it's obvious that you're refering to the bark.
When you use storm as a suffix, it's obvious that you're refering to the clouds.
Names are better when the suffix is something the cat has.

A name tends to work when either the cat has a suffix that looks like the prefix,
the cat looks like the prefix and is skilled with the suffix,
or the cat looks like the prefix and has a suffix-y personality.

The simplified version: the cat has a suffix of prefix.