What is a homotopy between $L_\infty$-algebra morphisms A $L_\infty$-algebra can be defined in many different ways. One common way, that 
gives the 'right' kind of morphisms, is that a $L_\infty$-algebra is a graded cocommutative and coassociative coalgebra, cofree in the category of locally nilpotent differential graded coalgebras and their morphisms are coalgebra
morphisms that commute with the codifferential.
Breaking this compact definition down into something more concrete, the category of $L_\infty$-algebras can equally be defined in the following way:
A $L_\infty$-algebra is a $\mathbb{Z}$-graded vector space $V$, together with a sequence of graded anti-symmetric, $k$-linear maps 
$D_k:V \times \cdots \times V \to V$,
homogeneous of degree $-1$,such that the 'weak' Jacobi identity
$
\sum_{p+q=n+1}\sum_{\sigma \in Sh(q,n-q)}\epsilon(\sigma;x_1,\ldots,x_n)
D_p(D_q(x_{\sigma(1)},\ldots,x_{\sigma(q)}),x_{\sigma(q+1)},\ldots,x_{\sigma(n)})=0
$
is satisfied, for any $n\in\mathbb{N}$. Where $\epsilon$ is the Koszul sign and $Sh(p,q)$ is the set of suffle permutations.
A morphism of $L_\infty$-algebras $(V,D_{k\in\mathbb{N}})$ 
and $(W,l_{k\in\mathbb{N}})$ is a sequence $f_{k\in\mathbb{N}}$ of 
graded-antisymmetric, $k$-linear maps
$
f_k : V\times \cdots \times V \to W
$
homogeneous of degree zero, such that the equation
$
\sum_{p+q=n+1}\sum_{\sigma \in Sh(q,n-q)}\epsilon(\sigma;x_1,\ldots,x_n)
f_p(D_q(x_{\sigma(1)},\ldots,x_{\sigma(q)}),x_{\sigma(q+1)},\ldots,x_{\sigma(n)})=\\
\sum_{k_1+\cdots+k_j=n}^{k_i\geq 1}\sum_{\sigma \in Sh(k_1,\ldots,k_j)}
\epsilon(\sigma;x_1,\ldots,x_n)
l_j(f_{k_1}(x_{\sigma(1)},\ldots,x_{\sigma(k_1)}),\ldots,
f_{k_j}(x_{\sigma(n-k_j+1)},\ldots,x_{\sigma(n)}))
$
is satisfied, for any $n\in\mathbb{N}$. 
This defines the category of $L_\infty$-algebras, sometimes called the category of $L_\infty$-algebras with weak morphisms.
Now after that long and tedious definition, the question is:
What is a reasonable definition of a homotopy between two (weak) morphisms
$f:V\to W$ and $g:V\to W$ of $L_\infty$-algebras? (And why?)
Edit: A lot of information pointing towards a definition of such a homotopy 
(or 2-morphism in $(\infty,1)$-categorical language) is spread out in the net.
Much on the $n$-category cafe, like in
https://golem.ph.utexas.edu/category/2007/02/higher_morphisms_of_lie_nalgeb.html
and in the nLab. However it looks like an explicit equation still isn't available.
I would do the tedious calculations myself, since I can get a lot of joy out of
such huge and delicate computations, but I'm unable to finde a calculable way to 
achive that goal. (Such a way should have the potential to apply to the higher homotopies too, hopefully leading towards an explicit description of the hom-space in this category)
P.S.: The tags are not very well suited, feel free to change them
 A: There is a plethora of model structures for L-infinity algebras (going back to Quillen of course, but notably described and related in the great article by Jonathan Pridham arXiv:0705.0344). Also structures of categories of fibrant objects. Each of these induces a model for homotopies of 1-morphisms of $L_\infty$-algebras, for instance a right homotopy given by mapping into a path space object. What these are can be worked out for each of these model category/category of fibrant object structures (and all these notions will be suitably equivalent).
An explicit model of such path space objects for $L_\infty$-algebras is discussed by Dolgushev in section 5 of his article arXiv:0703113.
See on the nLab at model structure for L-infinity algebra -- Homotopies and derived hom spaces.
A: One standard answer*, in which any reasonable (characteristic $0$ — I haven't thought about any other case) algebraic category can be given a simplicial structure, is the following.
Let $\mathbb Q[\Delta^k] = \mathbb Q[t_0,\dots,t_k,\partial t_0,\dots,\partial t_k] / \bigl\langle \sum t_i = 1,\ \sum\partial t_i = 0\bigr\rangle$ denote the differential graded commutative algebra (dgca) of polynomial forms on the standard $k$-simplex.  Here $t_i$ are in (co)homological degree $0$, and their derivatives $\partial t_i$ are in degree $\pm 1$ depending on whether you prefer homological or cohomological conventions.  It is straightforward to check that $\mathbb Q[\Delta^k]$ has (co)homology only in degree $0$, where it is $1$-dimensional.  Moreover, there are natural face and degeneracy maps between different $\mathbb Q[\Delta^k]$, making $\mathbb Q[\Delta^\bullet]$ into a simplicial dgca.
Given two $L_\infty$ algebras $V,W$ (or, really, objects of any reasonable category of "algebras"), one then defines the space of maps $V \to W$ to be the simplicial set
$$ \hom_\bullet(V,W) = \hom(V,W[\Delta^\bullet]),$$
where $W[\Delta^\bullet] = W\otimes_{\mathbb Q} \mathbb Q[\Delta^\bullet]$ is the $L_\infty$ algebra $W$ base-changed to live over the $k$-simplex.  It is reasonably straightforward to prove that this simplicial set satisfies the Kan horn-filling condition, at least when $V$ is "quasifree" — in particular, in your situation of "nonlinear $L_\infty$-algebra homomorphisms", the Kan condition is always satisfied.
Before I spell this out, I'm going to change your notation.  What you called $f_k$ I will call $f^{(k)}$, since it plays the role of the "$k$th Taylor coefficient of $f$".  That way, I can ask "what is a homotopy between two morphisms $f_0,f_1 : V \to W$ of $L_\infty$-algebras?"  
The answer is the following data: (1) a (nonlinear) homomorphism $f_t: V \to W$ that depends polynomially on a parameter $t$, with the correct evaluations $f_t|_{t=0} = f_0$ and $f_t|_{t=1} = f_1$; (2) maps $\phi^{(k)}_t : V \to W[1]$ (or maybe I mean $[-1]$), also depending polynomially on the parameter $t$.  These data must satisfy a certain ODE of the form:
$$ \frac{\mathrm d}{\mathrm d t} f_t = \operatorname{ad}_{f_t}(\phi_t) $$
Of course, this is really an infinite sequence of equations (which are equations to things that depend polynomially on $t$).  The $k$th entry on the left hand side is $ \frac{\mathrm d}{\mathrm d t} f_t^{(k)}$.  On the right hand side, the $k$th entry is computed as follows (up to a sign which I don't feel like working out).  Consider the equations saying that $f_t$ is a homomorphism; one of these equations is an equation of things with $k$ inputs $x$.  Sum over all ways to replace, in each summand in this equation, one of the occurrences of an $f$ by a $\phi$.  Such a sum is what I mean by the right-hand side.  In short-hand, what I mean is: there is (a sequence of) equations $M(f)$, such that $f$ is a homomorphism iff $M(f) = 0$.  The right hand side is $\frac{\partial M}{\partial f} \cdot \phi$.
In good situations like yours, all the ODEs that occur when studying $\hom_\bullet(V,W)$ are pretty well behaved.  In particular, their integral forms are contraction mappings in the appropriate sense, so the initial and boundary value problems are pretty easy to analyze formally.

*Here is an important (elementary) exercise to work out if you want to understand this "standard answer."  Consider just the category of chain complexes.  Then, for $k \geq 0$, $\pi_k\bigl( \hom(V,W[\Delta^\bullet])$ is the space of chain maps $V \to W[\pm k]$ modulo chain homotopies, i.e. it is $\mathrm{H}_k(\underline\hom(V,W))$, where $\underline\hom$ denotes the chain complex of all linear maps $f: V \to W$ with differential $f \mapsto [\partial,f] = \partial_W\circ f -(-1)^{\deg f}f\circ \partial_V$.  (Whether the shift should be $[k]$ or $[-k]$, and whether I mean $\mathrm H_{\pm k}$ or $\mathrm H^{\pm k}$ or ..., depend on your conventions, so I didn't work them out.)
