I think that where you are wearing a kilt would determine footwear as much as anything.

To a Burns Dinner on the weekend I wore smart brown leather shoes to match my brown Freelander sporran.

Last week when hiking in a tartan kilt I wore hiking boots.

Today I went for a walk along the beach in a Bear 4 yard casual and wore Teva leather sandals, which eventually came off (the sandals I mean) when I walked in the sea.
I agree that it may have looked a wee bit lady-like, but on a big empty beach - who cares?

I wouldn't wear sandals to a dinner and I wouldn't wear good shoes in the water.

All this illustrates the incredible versitality of kilts IMHO.

BTW, I believe that a velcro kilt is an ideal garment for the beach. Easy to get on and off and good for changing in and out of bathers after a swim in comple modesty!