Looking at your pay statement, it appears they structured this as a loan, which you paid back in 2019 with a "magic bonus". That's a good way to do that.
Loans are not taxed
Your arrangement had it that you got the $5000 in 2018, but would not keep it unless you started work in 2019.
Had you not started work in 2019 (a fact not knowable until 2019), you would have had to pay the $5000 back, and it would never have been income in 2018.
So it appears they did the accounting correctly for that instance. They posted the 2018 $5000 as a loan. Then, in 2019, once the signing bonus had struck, they seized back the $5000 loan repayment out of your paycheck, while simultaneously posting a $5000 magic bonus. So the effect on your paycheck was a wash.
As far as your pocketbook is concerned these canceled each other out, and it's six of one, half dozen of the other.
As far as the IRS is concerned, neither the loan nor repayment is taxable, but the $5000 magic bonus is taxable. In 2019.
If you want to see that in closer detail, look at your pay statement that you linked. You supposedly got $5000 bonus in 2018 and $5000 in 2019. But your pay statement clearly shows you got two $5000 bonuses in 2019, totalling the $10,000 you were promised. And notice how they're marked. One is marked Sign Bn Ln Pymt G&T on the gross earnings side, that being "Signing Bonus Loan payment G&T". That is the "magic bonus" that pays off the loan. Then over on the "Other deductions" side, you see Prepaid Sign Bn Ded which is them intercepting the magic bonus to use it to settle your loan.
So it's both credited on one side as taxable income, and debited on the other side as a loan payback (since the money was paid in 2018).
If you reported the 5000 as income in 2018, you did so as your own flight of fancy, without support of a 1099 or W-2 telling you to do that. You will need to amend your 2018 taxes using a Form 1040X, to remove that income from 2018. Then do the same with the state. This will net you well over $1000 of refund.
For the explanation, you simply state "Did not realize $5000 signing bonus was actually loan". This will surprise no one at IRS, it's a common mistake, and will fully explain the matter since they don't have any 1099 or W-2 data on file for that amount.