My money is on it being the APU holding things back. Basically your RX 460 and A8-7600 were perfect for each other. You could get all the performance out of both depending on the game. The RX 580 is WAY more GPU than the APU can handle. In games that load the GPU more you'll see some improved performance, to a point, but in games where the APU is the part being stressed you'll see no performance gain at all.
So, your APU is the problem here. A low end Ryzen like the 2200G will provide a SUBSTANTIAL (something like 80%) performance increase over your current APU and unleash the RX 580. You'd even get around a 30% performance increase from something as modest as an Athlon 200GE. It would still be a bottleneck on the RX 580, but not quite as badly.
If you monitor your CPU and GPU usage in games you'll see that your CPU will be near 100% usage and your GPU usage will be pretty low. This indicates a CPU bottleneck.
As for the deal you got on your RX 580, it was probably a mining card, which means it was pushed hard for extended periods of time and that might lave lowered the life of it, but it shouldn't have impacted performance too much.