It depends on the context. Just scaling a npc is not really satisfying. You should add something which requires a new strategy to approach the enemies other then hitting the attack button more often.

E.g. an elite version of a npc should have some extra feature/skill the standard version does not have.

Taking your example, a standard goblin has almost no armor, whereas a champion is armored (choice of other attack spells) and an elite goblin is able to call reinforces.

Does it feel cheap?

yes. it doesn't increase the type of monsters in the game, only the range of strengths they come in, and what they are called.

Take it to the extreme: what would a D&D game be like with only kobolds? sure they may go from level 1 to level 50 in toughness, but they're all still just kobolds.

In a medieval fantasy setting, which different names could otherwise be used (rather than champion and elite) to signify higher level enemies?

about a billion different ones. just take a look at a few games to get some ideas. or try a thesaurus.

1. No it is not cheap. It is either "done well" or "not done well". Diablo II was awesome and it used this system to its fullest potential. The question is how to do it effectively. It's near pointless to increase monster hp and dmg by x% on the next difficulty level if your character's hp and damage have also risen by x% as well. Nothing's changed in that situation. This system should only be used for enemy monsters in my opinion. A more creative system should be used for the main player (once again this was done in Diablo II).

2. These words make me think powerful medieval: Legionnaire, Centurion. These are not medieval terms though. I believe Centurion is Roman. Also I stole these 2 titles from vanilla WoW which used them as part of their pvp ranks.

I believe Centurion is Roman.

They're both Roman.

https://en.wikipedia.org/wiki/Legionary

https://en.wikipedia.org/wiki/Centurion

Read up on medieval times, you'll find lots of titles appropriate for the time period.

There are a lot of creative ways to increase the difficulty of a creature in a positive way. Only increasing their stats simply makes things harder, not more interesting or fun. I don't think a game should ever be about being harder solely for the sake of it. Dark Souls, for example, was not meant to be such a brutal game. It simply came out that way as a product of the design.

As Scouting Ninja mentioned, diablo gives the stronger enemies special abilities. In Diablo 3, these abilities were randomised. They were all part of a central pool and when an elite monster spawned it would select a number of abilities from that pool that you had to deal with.

Another way to increase difficulty is to improve the enemies AI.

Or you might change its role from 'stronger enemy' to 'group commander'. The elite monster of a pack of goblins is able to command those goblins as an army, rather then having them fight you haphazardly.

Or even change their fighting style. A goblin may wield a small spear to strike at its target. An elite goblin may wield a large spear, using it expertly to attack from a far range, perhaps incorporating more attack variations to mess with the players rhythm.

There are endless possibilities to make an enemy harder. I always notice when a game simply increases an enemies stats and pretends the enemy is now 'harder', and I always hate it. Trust me, it is the perfect example of anti-fun and lazy design. Do not do it.

1. I find merely increasing a monster's entire state line by x% to be cheap and lazy, yes. There are so many ways to increase difficulty that are more inventive and plenty of them don't take much more effort. Even increasing an enemy's states non-uniformly is better, perhaps by accentuating the monster's role. Got a bulletsponge monster? The upgraded version might actually do less damage but take three times the punishment to put down. That sort of thing. Something that changes or at least sharpens the player's situation rather than a lockstep increase in stats to keep up with the player's abilities and changes nothing about how they deal with them.

2. As other have said, simple military ranks from any time serve well. If the enemy's are monstrous rather than intelligent/humanoid you could use words depicting age "Young, Elder, Ancient" and such. Pretty much any system of descriptors works well, and bonus points if its serves some other purpose (ie, a certain class of enemies uses "_, misshapen, mutated, Abomination" as difficulty ranks, and also clues the player in that certain attacks such as Holy damage will work better).