Building on the answer of @manassehkatz, I think we might be able to tweak things to work.
As previously mentioned, kelp (the highest calorie seaweed I've managed to find) only had 43 calories per 100g. Even spuds have 93 calories. However, let's try and solve a few of the problems.
Caloric Intake
The main issue highlighted in @manassehkatz answer was that with such a low-calorie food, your people would need to be eating a lot of seaweed to meet your 2250kcal daily intake to stay healthy. 5.2kg a day is a lot. About double what it would take in cooked potatoes (2.4kg).
However, is 2250kcal necessary?
Your humanoids weigh between 50-80lbs (~23-36kg). Baka pygmies in Africa weigh on average 53kg for men and 46kg for women. Not quite as light as your seafaring herbivores, but let's take that as an upper bound. Now, trying to find a recommended caloric intake for little people has proven to be depressingly difficult. Closest I've found is an offhand mention of 1000-1400kcal per day. Let's fudge some numbers a little and say that the upper bound for our heavier modern little people is roughly equivalent to what your lighter but more physically active mariners need.
So, 1400kcal/day. That's a little more manageable.
Assuming your people have been cultivating seaweed for a reasonable amount of time it's not too difficult to believe they'd cultivate a more nutritious variant. If we take wild rice (101kcal/100g) vs domestic rice (129kcal/100g) as an example, then we could conceivably bump the caloric content of domesticated kelp up to 50kcal/100g.
Running the numbers again, our leaner more efficient herbivores now only need to eat 2.8kg of kelp per day. Much more manageable :) even wild kelp at 43kcal/100g gives 3.3kg which isn't insurmountable.
Oh, and the 43kcal/100g for kelp is a figure for raw kelp. Cooking tends to increase the caloric density of food, so there's wiggle room there too despite not being able to find a figure for cooked kelp.
Area
Next, we need to find out how much area is required to grow enough food to support your population to see if kelp is viable as an agricultural staple.
Luckily, I've come across this article detailing the aquaculture of various different seaweed species including yield per hectare! Perfect :)
Let's take good old spuds as an example of typical agricultural efficiency. With modern agriculture, we can produce 17.4 tonnes of potatoes per hectare (17400kg per 10000 square metres, or 1.74kg per square metre). I'm not sure how far potato farming has come since the middle ages, but I'd be willing to bet that this yield is significantly higher than a medieval one. Still, it's a good upper bound.
Our kelp (wakame) produces about 10kg of wet weed from 1m of rope using rope aquaculture (and is less labour intensive than nori farming which is good). Let's say the density of rope aquaculture is one rope per square metre (might be able to squeeze two in based on pics of the plant from google), we're looking at over 5x the efficiency of wet weed compared to potatoes. From what I gather, wakame is eaten wet so there's no funny business with comparing dried calorie density vs wet.
This might just work...
Population density
From the above, we can hazard a guess at the population density your aquaculture can support.
If each mariner needs to eat 2.8kg of kelp per day, and each square metre of aquaculture produces 10kg then each mariner will need 102 square metres of aquaculture to survive for a year producing 1022kg of kelp. With wild kelp, the figure is 120 square metres.
Compare that to good old spuds and you'd need 314 square metres per mariner per year using modern techniques. Seaweed's looking pretty good now!
So like for like, your mariners can support roughly 3x the population of their land-based potato-eating cousins.
As a rule of thumb, there's a medieval source that claims 1 square mile supports 180 people all-inclusive (not only farmland but housing and roads and inefficient uncultivated land).
Now, including their smaller stature and more efficient aquaculture, we can support 4.96 mariners for every one person (based on 2250kcal/day people eating potatoes, which isn't exactly rigorous but hey ho). So, we end up with a figure of 4.96 mariners per square mile.
So using the medieval model of land usage we end up with our 1000-mariner settlement spread across 201 square miles. A little less than Lake Winnebago.
Further consideration
How herbivorous do you want them to be? In the wild, you'd be surprised at how blurred the line is between herbivores and carnivores. Many animals you'd assume to be wholly herbivorous eat a surprising amount of animal matter.
If you don't want them to actually eat meat, how about deep-frying your kelp in animal fat? Plenty of blubbery animals in the cold waters where kelp grows best, and from my cursory research deep-frying adds roughly 100-120kcal per 100g. Digesting oils and fats from animal sources is digestively little different from oils and fats from plant sources, and medieval people tend to have a lot less moral scruples when it comes to what they eat. Food's food after all...
