Using MSOL for solving BIDS problem
The $O(5^kk^3n)$ is linear in $n$ as well and $O(n)$ for bounded $k$.
The Courcelle, Makowski, Rotics paper does not give explicit/good upper bounds for the contants hidden in the big-O.  If you want to make the dependency on $k$ explicit as in $O(f(k)n)$, then additional work is required.

See "Faster Algorithms on Clique and Branch Decompositions" by
Bodlaender et al (MFCS 2010)  for recent algorithms for domination-style algorithms.