Cotton was available, it just wasn't commonly used in everyday clothing because it was probably a pain to process. It was blended with linen to make fustian of course. One problem to is that Medieval people are documented to refer to cotton as 'wool' so things get tricky. There are cases of Medieval Europeans referring to cotton plants as wool-bearing plants. So who knows what they really meant all the time! Cotton fabric was most common in Italy (and by most common I mean rare, but more available than the rest of Europe) from what I know, and eventually spread during the renaissance.
For stuffing, you don't need to spin it in to thread, and if there's a seed or two in there, who cares. But yes, wool/straw/tow/hair are all appropriate stuffings.
