A - Let me use new company to represent a new company with an established business model, like a restaurant, like a new shoe manufacturing plant, or a new transport company.
B - Let me use start-up company as a designation for a project of company in search of a business model. Startups, in reality, are not yet companies, they are still projects of companies in search of a successful business model and customer fit. So, a startup is like an experiment being done. The startup can be called a company only after finding the right business model, a customer fit, and when it starts scaling. Only then, the procedures and internal standards are ready to be documented.
So, for situation B it is too early to certify. For situation A, I think it is easier to get ISO certification than with an established company (with same resources and motivation). An established company has to unlearn some practices and that it is not always easy.