I’d really like to get into this game, finding it super hard.
Even during the “tutorial” I had to google several times how you are supposed to do the stuff.
In story mode you have to play so many different characters, can’t handle even one of them properly.
Is the game supposed to be like this? First 10 minutes are harder than the endgame of other games it seems…
Do you have any tips where to start?
Focus on learning the special moves of your favorite characters, just practice practice practice in practice mode till you can do their moves super reliably. Dont play story mode against the computer for awhile. Play against friends, and have them learn the game with you if they like it too, friends make everything funner. If your friends dont like the game, find other people to play the game with and become friends with them too. 
Yes, fighting games are a ton harder than normal games. A few people I played against at an anime con this weekend went to the command list section where it lists the moves and they were totally lost. 
These games are like playing instruments, you have to practice every day for hours and make sure your hands get muscle memory for stuff in order to play them well.
Orochi is very correct in saying learning these games is much like learning an instrument - except you can beat people with them without going to jail :P. Many modern games are made so they make you feel like a champ even if you’re totally horrible - autoaims, scripted events, invulnerable teammates quietly doing things for you, and so on. Fighting games are not like that. This is a genre that doesn’t hold your hand - like an actual instrument you’re learning, it brutally tells you you suck ass. But improving is all the sweeter for that. KOF13 is one of the first things I found actually fun to practice.
The three-character team is a staple of KOF. Don’t worry though, even if the characters look very different at first and also are very different in practice, there’s a subtle, invisible common thread with them all: KOF13 is a system-first type game design.
What it means is that all characters share the ability to do certain things - they can run, they have four different jumps so they’re all quite mobile. Up close, you can use very basic tools to make your opponent guess between a hop attack (must be blocked high), throw (opponent must stand up to defend and not block), and a low (must be blocked low, leaving you open to hops and throws) so you can get damage in. On defense, everyone has rolls, guard cancel rolls and guard cancel blowbacks to use. This lends a coherent feel to the game - every character “plays KOF”, so to speak, and it’s a skill that really translates between characters. KOF system + character’s tools = character’s gameplay. So if you learn KOF well on one, it helps you out a ton with the others, too.
If you’re really new, I’d try to get used to your characters’ normals and specials so you have a clue what to do. As for practice, the most basic thing to do is to practice the fundamentals - being able to do hops consistently, being able to do the special moves cleanly, run-up throw, some short, meterless combo for each one (You can get some quick basic combos - practical ones - from Dream Cancel’s wiki here). You don’t need the absurdly hard and long stuff against other beginners. Just being able to convert openings into something at all is enough.
KOF13’s trials are truly trials in their own right - apart from the first couple ones they are masochistically hard combos that use meter inefficiently. They’re there to be a challenge to your execution, not to be something practical you’d actually use in a match.
Here’s a whole crapton of useful links to check out for learning KOF and fighting games in general.
Welcome to the long road of improvement. Hope you have fun along the way ^^