Hard starting - suspect your starter motor ? check this out
 

This is the pre-upgrade stater motor speed demonstration when in good order (new brushes just fitted). Note accelerator held down on purpose so it would not start then accel. off on 2nd attempt .


This is same starter motor with worn out brushes . Two of the four brushes were at minimum spec (7mm long) the other two were at 10mm length. Worth noting that at this speed the car would not start at all .


Here is an upgraded starter motor for comparison .

Do you think worn brushes would make a difference when the car is warm? I've searched about the warm starting problem, and as far as I can tell there is no real definitive answer yet. My car won't start after I've turned off the car until its cooled down for about 10 minutes, then it will start. My starter does sound a lot like the second, worn out starter, so I'm just wondering if maybe that could be a problem.

^ you should check your compression

I know, the biggest thing holding me back is I'm scared it will mean I need a new engine lol. I'm in Germany and I've been told they don't do the new engine deal here, so I'm kinda screwed.

Welll if starter motor is slow AND compression is weak . Then warm starting will be a big problem .
If you have bad compression but don't want to get it fixed having the fastest starter motor and best battery you can get will save you a lot of heartache .

Thanks

My car sounded like the first youtube clip with the old starter and eventually it led to not starting at all when it was hot... Sure enough it had low compression... I would bet you need a new one aswell.

Added video of upgraded startermotor