How to fix holes in linoleum so that I can lay down sticky tiles over it
For small holes I just use spackle. Mix it up and use a putty knife working any air bubbles out. You may need a second application if the holes are deep. 

If the holes are larger, after I have a nice even fill and when dry I will use a paint primer so the tiles will stick better, this is a good idea with self leveling compounds also so the tiles will stick and not have the edges roll up.