Let $f:(0, \infty) \longrightarrow (0, \infty)$ be a monotonously increasing function (in fact, a step function) and let $P$ be a polynomial of degree $N$. Suppose I know that for some $k$, the limit $$A:= \lim_{\varepsilon\rightarrow 0} \int_0^\infty \frac{e^{-\varepsilon s}}{s^k}(f(s) - P(s))\, \mathrm{d}s$$ exists. Can I conplude that $f$ has an asymptotic expansion which is given by $P$? More precisely, can I conclude that $$\left| f(s) -P(s)\right| \leq C s^{k-1}$$ for some constant $C>0$?

No. The limit can exist due to cancellations, without $|f-P|$ being as small pointwise as you hoped for.

Let's take $k=0$, $P(s)=s$, and $f(s)=n+1/2$ on $n<s<n+1$. Then $$ \int_n^{n+1}e^{-\epsilon s} (f(s)-P(s))\, ds =-e^{-\epsilon(n+1/2)}\int_{-1/2}^{1/2} te^{-\epsilon t}\, dt = \frac{\epsilon}{12}e^{-\epsilon(n+1/2)}+O(\epsilon^2)e^{-\epsilon n} , $$ so the sum over $n$ of these terms equals $$ \frac{\epsilon}{12(1-e^{-\epsilon})} + O(\epsilon) . $$ Thus the limit exists ($A=1/12$), but $|f(s)-P(s)|\ge c>0$ for arbitrarily large $s$.