Why can all solutions to the simple harmonic motion equation be written in terms of sines and cosines?
This follows from the uniqueness theorem for solutions of ordinary differential equations, which states that for a homogeneous linear ordinary differential equation of order $n$, there are at most $n$ linearly independent solutions.
The upshot of that is that if you have a second-order ODE (like, say, the one for the harmonic oscillator) and you can construct, through whatever means you can come up with, two linearly-independent solutions, then you're guaranteed that any solution of the equation will be a linear combination of your two solutions.
Thus, it doesn't matter at all how it is that you come to the proposal of $\sin(\omega t)$ and $\cos(\omega t)$ as prospective solutions: all you need to do is
- verify that they are solutions, i.e. just plug them into the derivatives and see if the result is identically zero; and
- check that they're linearly independent.
Once you do that, the details of how you built your solutions become completely irrelevant. Because of this, I (and many others) generally refer to this as the Method of Divine Inspiration: I can just tell you that the solution came to me in a dream, handed over by a flying mass of spaghetti, and $-$ no matter how contrived or elaborate the solution looks $-$ if it passes the two criteria above, the fact that it is the solution is bulletproof, and no further explanation of how it was built is required.
If this framework is unclear or unfamiliar, then you should sit down with an introductory textbook on differential equations. There's a substantial bit of background that makes this sort of thing clearer, and which simply doesn't fit within this site's format.
How can we assume so plainly that it should be sin or cosine only
It's literally just a guess. Those're obvious solutions which can be verified easily, and when they're such straightforward functions, you'll soon just be able to notice them. It's the like when you have an equation like $f'(x)=K\times f(x)$, you just see that the solutions are exponentials. After that, you know that for a differential equation like $f^{(n)}(x)=Kf(x)$ you can have upto $n$ solutions, so you aren't missing anything when you consider the sine and cosine.
It's a nice idea to not waste time/effort/space formally solving such equations when the solutions are canonical.
These are all good and correct answers, but I will answer from a different perspective.
Any linear-differential equation of degree $n$ has $n$ linearly independent solutions, ie. these $n$ solutions span a vector space, with sets of solutions forming a basis.
For simple harmonic motion, the differential equation is:
$$m(\dfrac{d^2x}{dt^2})+kx = 0$$
As stated in other answers, one can take the solutions to be linear combinations of $\sin(\omega t)$ and $\cos(\omega t)$, or one could take $\exp(i\omega t)$ and $\exp(-i\omega t)$. These are both sets of linearly independent functions, and both pairs solve the equation, yet they are not the same functions - they are two different sets of basis functions.
To get from one set of solution to another, one needs to change the basis.