I guess "getting a new PC" would be relative since you can most likely keep the current case and power supply at the very least. Again, back to the joke I had made lol
Depending on the game, gaming with a 4K TV at native resolution would be kinda tough so you'd definitely need to sacrifice a bit there, i.e. running games at 1440p or even 1080p.
If you're looking to only "upgrade" what you have, then I'd focus on the CPU first. As said before, that'll cascade into also needing a new motherboard and RAM. I don't think any of the CPUs compatible with your old motherboard would be worthwhile at this point since having more cores will help a lot.
Also, a lot of new hardware was just announced so buying at this exact moment is a bit awkward since you could buy last year's stuff or wait a little (and fight the huge demand) to get the new hardware that perform a good amount better, which hasn't happened in a while.
CPU: AMD Ryzen 5 3600, used Ryzen 7 3800x, or wait a bit for the Ryzen 5 5600x
($180-300)
Get whichever is the cheapest.
You can overclock the 3600 to perform as good as the more expensive 3600x and 3600xt without spending more.
The 3800x would be more useful for editing since it has more cores and more threads.
The new 5600x performs much better in games than CPUs that cost way more, but you'll need to wait like a month for it to be available. You can look at some of the benchmarks online to see if you think it's worth the wait.
Motherboard: Any good B450 or B550 motherboard
($70-170)
Shouldn't matter too much what you get, just get what you need (i.e. do you need a lot of USB ports? Built-in WiFi? Does your case have front USB 3.0 or Type C? RGB lights????).
If you choose to wait and get the 5600x CPU, then you'd want to get a B550 board. Otherwise, a B450 would save some money but may not be as high quality.
RAM: 16GB or 32GB of DDR4 RAM
($100-150)
You'd want to get 2 sticks or more totalling that amount. A single stick will run slower. Additionally, to optimize performance, you'd want the RAM to be at least running at 3200 mhz as those Ryzen CPUs like fast memory.
If you plan do a lot of multitasking, such as rendering and browsing the internet or playing games and having a lot of windows open, then getting 32GB would be better in the long term. I currently have 32GB and the only time I have surpassed 16GB is when I have over 100 tabs open and a virtual machine open for programming. I personally don't edit videos that much so I don't know what the worst case scenario for that would be, but 16GB should be enough.
That should be like the bare minimum of an upgrade to get going. Based on however much you want to put into it, you can scale this to get a better CPU. Or if you want to game at native 4K, you'd need to upgrade your graphics card. The new RTX 3070 is $500, but probably won't be in stock for a while due to high demand. The alternative AMD RX 6700XT would be good too when it becomes available soon. But what you have, the RX580, should be definitely good enough for 1080p gaming for a little longer (if the RX 580 is the 8GB version and not the 4GB, it's all very confusing).