To be fair, the mission statement says quite clearly just before that, that one of their main goals is to seek out new life. I would see that as them acknowledging some peoples might exist somewhere before they show up. So that sort of disqualifies the thought that they might just be looking for a planet where no life is or ever has been.
Space stretches out in all directions. And space, in addition to being the final frontier, is big. I mean really big.
"You just won't believe how vastly, hugely, mind-bogglingly big it is. I mean, you may think it's a long way down the road to the chemist, but that's just peanuts to space."
~ Douglas Adams
Even if the planets they find and land on do have life on them, if the intelligent life forms they find there haven't reached the stars and set a course for Earth, then the path the Enterprise took to reach it likely hadn't been traveled before by anybody. If they were visited prior by some other star faring race, the path they took was likely different than the one our crew would have taken.
It's of course also really a statement of courage. They were setting off on a journey to places where they weren't sure what they'd find. To boldly go, to be bold, to stay strong, to stave off fear in the face of the unknown, and not let that fear alter your path.
The show is called Star Trek. Trek, as in, it's all about the journey. The path they're taking hasn't been trodded before by anyone.