Go to the Check Register screen from the Tasks > Check Processing menu. Choose the bank account register that you want to view. Then, click the List button on the toolbar and then select that vendor check from the list.
Once it's on the screen, click the V button on the toolbar to void the check. This will void the check, and will mark those bills as unpaid again. I'd recommend that you use the same date to void the check as you did on the original check.
You can then go back to the Pay Bills screen and just pay one bill. After that bill is paid, and you've closed out of the Pay Bills screen, then you go back and select the other bill to be paid.
Return to Entering/Paying Bills