When a paladin in the game I run went into the local store ran by an ex adventurer, he went to the back to see the fancy swords, and asked if any looked like his holy symbol. The god he follows is illegal in that world, so I thought it would be cool if the shopkeep had one, so I narrated an old padded box that she takes out with a sword that exactly matched his holy symbol (which is a sword in a circle). I narrated a tingling feeling when he touched it. But then I realized; he's level two, the game has barely started, and I had him buy what seems to be a potentially extremely powerful magic item for 60 gp. I don't want to backpedal lamely and make it weak, but it seems like a sorta dumb way to get a great item. What should I do?
To clarify, neither I nor the player know what item he has. I don't want to make it a lame +1 sword or something, when I narrated it as something powerful. I was thinking of tiering it, at 1st tier it does nothing, second tier 1d6 extra radiant damage and +1 AC or something, add an extra d6 and armor boost per tier, by L17 it'll be +3 AC and 3d6 extra radiant, but I am afraid that might be too good for something he bought and didn't even do anything to get.
Thanks for all of the good answers. I had a hard time deciding which to accept.
Best Answer
Welcome to the wonderful world of "winging it"
It's an old DM/referee mode that's been around since before D&D was published.
Your reason wasn't a bad one
A common magic item costing 60 GP is within DMG and Xanathar's Guide to Everything (XGtE) cost bounds for common magic items. (It looks like the paladin was offered something like a 'friends and family discount' by the shop keeper). You are right to not make it a +1 sword. Make it a sword with a modest amount of magic on it. The fact that it is magical at all means that it handles the resistant / immune to magical attacks already: this is good for a paladin who may be battling nefarious beasties or wererats.
That tingly feeling is a good idea, narratively.
What you have done is similar to foreshadowing: something good is coming that you get to experience with the player. You can design this up front from bottom to top, but emergent growth is a cool way for this sword to grow with the character. I'll cover that also. Since you have a deity involved, you can intertwine the sword's growing powers with 'what the deity wants/needs their holy warrior to do' or something similar.
Unlocking powers as they level up can be a great technique
The sword can grow with your player's character but there are also two side benefits to what you have done:
That's a path (NPCs hunting the item bearer) I have taken with a similarly tiered/unlocking item in the shared world that I DM with my brother.
Caveat: watch out for overpowering the item.
It's easy to overpower an item by piling stuff on. Your initial idea looks like it compares favorably with the tier progression of rarity values in the DMG, and the common rarity from XGtE. I recommend that you do this: have it progress from common to uncommon to rare to very rare as you enter each tier. If you look at the common magic items in XGtE, they each have a little magic.
Here's a way to tier the item.
(@PixelMaster also has great advice on this in their answer).
Tier 1 (where you have it) sword is magical. Advantage on persuasion checks when dealing with clergy or followers of that deity (perhaps only if the symbol is shown/displayed, up to you).
Tier 2 (Uncommon) 1d6 extra radiant damage or +1 AC
Tier 3 (Rare) 2d6 radiant damage or +2 AC and casts light cantrip at will (command word = deity's name).
Tier 4 add 3d6 radiant Damage or +3 AC and light cantrip (command word) and one other feature.
Pacing the item's growth.
Option: Legendary, named for the PC, near level 20
As your player's PC closes out their adventuring career, they'll do something impressive that saves the world, or something that really pleases their deity. Add one more power to put it in the legendary class of item (compare to DMG items that are Legendary) and have the player's name emerge along the blade in radiant runes. Example narrative sequence ...
I've seen this done very well once
In AD&D 1e/OD&D campaign we were in, the DM 'winged it' with a magical sword that our paladin found on a random treasure roll. As the DM rolled the abilities for it (it was an intelligent sword) he decided that it would be overpowered at level 3. {We didn't know this until the game broke up a year later}. Every other level (5, 7, 9) the sword would talk to the player and tell him "by the way, we can do this also" - and, the DM changed his mind at level 7 when the fly spell unlocked. We only had a few more sessions after the ninth level adventures before the group broke up (people moving). That's when the DM told us what he'd done. The player liked it so much that he decided to keep the sword (as an idea) and use it as a quest item called Pillagar's Sword for his next campaign.
Caveat: double check for OP at each progression
I've seen this idea backfire: it happened to me when I ran an Empire of the Petal Throne campaign (a setting that was very OD&D in style and feel). I had one of the deities (Sarku) bless a character with a dagger that added powers each time he leveled up. By sixth level, he was more or less "the it guy!" I'd done it out of sheer inexperience.
You are right to be wary of that.