I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity and I am not sure where I might have went wrong. 

First I will show the algorithm, argue about its correctness and then what I tried on finding the time complexity.

So given a Graph $G = (V,E) $ and $n = |V|$ and $m = |V|$  and the case of k > 3 we would use the following algorithm:

 - Find every 3-Clique first in $O(n^3)$ (using three for loops for checking every possible triangle) and using hashing whether a triangle was already added or not. 
 - Now we have the set $M := \{(i,j,k) | i,j,k \in V \land (i,j), (i,k), (j,k) \in E \}$ of triples of all disting 3-cliques. 
 - Next we use the list of 3-Clique to search for 4-Clique through looking at every adjacent node $l$ of of every triple $(i,j,k)$. 
If one the the adjacent nodes is connected to all $(i,j,k)$ so that $(l,i),(l,j),(l,k) \in E$ we have found a 4-Clique.  
 - We proceed this process for every s-Clique with $s \in \{4,...,k \} $ usingal found $s-1$ clique

For the correctness of the algorithm it should be enough to show by induction that every s-clique consists of s-1 possible (s-1)-cliques

I tried to estimate the time complexity the following way: 

 - Worst Case Complexity is finding a n-Clique in $G$. So this means we have $ m = n(n-1) $

 - We would have to do  $(n - 3)$-Loops for finding every s-clique in the sth loop.

 - In every loop we have less n s-clique where every s-clique might have maximum $s(n-1)$ adjacent nodes to look at. 
 - Since we have less then n s-clique this would mean looking at $n*s(n-1)$ possible edges for finding a new s-clique.

This would sum up to $O(n^5)$ using gauss sum for every s-clique, but this would mean clique is in P and this seems a little bit to easy to be true.