I've completed all of the cups, all of the time trials, and all of the challenges, excluding free race and arena modes because there aren't any requirements to get unlockable characters, custom paint, and car parts on those modes.

Nice run, but if this category were to be put on the leaderboards you would be required to purchase all the car parts and paint jobs. The game has an inbuilt percentage counter so technically this run isn't 100% completion.

Do you simply have to beat all of the bosses in Challenge mode to beat it or do you have to beat every single challenge to beat Challenge mode?

I've finished all of the cups, all of the time trials and all of the challenges but I have not gotten all of the car parts, I didn't know it was part of getting 100 percent completion, I think I have to start the game over.