Games actively train a player's "skill". I define the player's skill as the player's ability to use the mechanics in the game to meet the challenge the game is presenting.

The way to make a game more replayable, then, boils down to 3 things:

1) Make the game more challenging. This forces the player to change their approach to problems (because their old solution no longer works)

Multi-agent games do this by having a variety of opponents.

Single-player games do this by ramping up the difficulty, generally by making the execution requirements tighter. More complexity, or less leeway for mistakes.

Leaderboard-type games do this by using a "best score" as the goal. (e.g. Rhythm games, racing games, etc.)

2) Adding and/or removing mechanics that force the player to change their approach to problems. Again, this is either because the old solution doesn't work, or you must use the new mechanic in the solution.

3) Add randomness, mimicking either of the above. (e.g. Roguelikes/lites, deckbuilders, etc.)

There's also the possibility of extending play-ability by "creating new content". I think this isn't really "re"playability, since the generated content hasn't been "played" before, but procedurally-generated content and sandbox games have this sort of code-generated-novelty-as-replayability.