This was mentioned by someone else in a now-old thread, but I want to outline how it could be done at the semi-technical level:
As far as I know, blocks that are placed by players have a tag enabled on them while those that are generated/made by lava, placed by endermen, etc. do not. The update could notice those blocks when the option to 'ruin old player structures' is enabled.
There would be a 10-20% chance for every block to be decayed then. Examples of decay include cobblestone becoming moss stone, oak wood becoming dark oak wood, torches becoming redstone torches, and any block with a slab or stair equivalent becoming that slab or stair. There would also be a chance for some blocks to be removed entirely.
In old minecraft updates, the idea of torches burning out and having to be re-lit was joked around with. Why not make this a thing, then? It could be optional the way waterlogging is optional. Another idea often suggested here is iron rusting - it's not steel, it's just iron. Iron armour rusts in rain. Iron bars rust when near water. Even gold can rust very slowly over time, and there is a lot water near the gold in ocean monuments.
Actually, player-placed blocks have no special "tags" - there is just no way for the game to save such data given that the save format only allows for a block ID and data value, which is why if you name or enchant a block in the anvil and place it it will lose them (the exception is tile entities, which are special blocks which can store additional NBT data, like chests and furnaces, but due to being resource-heavy they are only used for such special blocks). Otherwise, only a few blocks which do not naturally generate could be detected and this excludes most blocks players build with and you would not want your e.g. beacons to be ruined.
Didn't you mention player-placed leaves act differently from ones grown from saplings or world-generated though? What's the difference if it's not in a tag?
It isn't a tag; the game uses the same 4 bit metadata that all blocks have (or had; 1.13 made every single block a separate block, which does not mean that they should double the number of blocks just so the game can tell if any block was player-placed since that will double the amount of resources and the time needed to search through the block list every time one needs to be referenced; performance in 1.13 is already terrible enough - new world creation in TMCW is literally an order of magnitude faster despite more complex world generation. Even if you do not think performance is an issue it is for many and it could always be better, hence why most players use Optifine, and that only addresses rendering, not core code like how blocks are handled).
While many blocks do not use metadata or all 4 bits and could (if it had been added before!) use a bit to tell whether they were player-placed it is not possible for blocks like wool to use it because they use all the available bits, and some blocks like flowerpots and beds were even turned into tile entities because 4 bits (16 states) wasn't enough (flowerpots could not contain every flower added in 1.7 otherwise, likewise I did the same in TMCW so they can represent 60 different plants (126 variations) in one block, and beds use metadata to store their direction and whether they are the head or foot).
This is also what I was referring to by "only a few blocks which do not naturally generate could be detected" - including player-placed leaves, or any wool color that doesn't naturally generate - but not blocks like cobblestone, wood planks, and so on because they naturally generate and have no means to differentiate themselves from player-placed blocks (even tile entities could be a problem since older versions simply did not store any "player-placed" data, aside from a custom name, and this thread is talking about upgrading older worlds, plus Mojang would have to devise some way to handle all blocks consistently, such as adding a new data layer to the chunk format which is an array of 4096 bits per section which are set to 0 = natural, 1 = player-placed - and this could only be applied to blocks modified since they added it).