Any company we start would always be a start-up, right? Would "started a company" mean the exactly same?
Not necessarily. There's quite a number of definitions:
start-up: a new small company or business, especially one whose work involves computers or the Internet (Longman)
Wikipedia has an insightful section about this very topic. Here are some definitions:
A company, a partnership or temporary organization designed to
search for a repeatable and scalable business model.
According to this definition, if you start a restaurant (where the business model is well-known, so no need to search for it), you are not founding a start-up.
A startup is a company designed to grow fast. Being newly founded does
not in itself make a company a startup. Nor is it necessary for a
startup to work on technology, or take venture funding, or have some
sort of "exit". The only essential thing is growth.
A recently started small "mom-and-pop" store that has no plans to conquer the world would probably not fit this definition.
There are more definitions, and not every new company would be a start-up according to all (and, I think, most) of them.
So when people say that someone started a start-up, they most likely mean a new, ambitious, trailblazing (possibly, tech) company that's trying to disrupt the market and grow super fast.
Edit: It's been suggested by others that "started a start-up" is somewhat tautological, and I tend to agree. At least in writing, I'd prefer "He founded a start-up" or similar.