Paper is countable.
Page is countable.
Hair is countable. (True, it is easier to count the hairs on your head after you have cut them off of your head.)
I am not sure I understand your English teacher's comments. (I suggest that you refer her to this website.) Whatever its shape, hair is hair. True, you would not, for example, say a person has red hairs but that a person has red hair. But that person's red hair is still countable.
Stars are indeed countable. Saying that they are countless simply means that there are so many that we could never count them all. They are so numerous that we could never put a number to how many there are.