I have a language with CVC syllable structure and a series of prenasalized consonants. As written, therefore, a word like /anda/ would be distinct from /aⁿda/. I can barely grasp the difference here, and even less so how to romanize this. Is it realistic to have an allophonic process turn /anda/ into [a.ⁿda], or vice versa?
It's perfectly reasonable to get rid of that distinction, and have
/ⁿd/ be treated exactly the same. Many languages in the Bantu family (the family that's most famous for its prenasalized stops) lack that distinction.
If you want to keep the distinction, it would probably be considered contrastive syllabification (the way the consonants are grouped into syllables is significant), which happens but is pretty rare. Googling that term will get you some more information on how that tends to work.
I don't think there is a difference between /aⁿda/ and /anda/.
There doesn't need to be any difference. If a diphthong can constitute a single syllable (as in "aisle," "boy," and "cow") so can a prenasalized consonant. A little practice can get you used to saying and hearing [nda] or [mbe], for example, as single syllables.
But if you WANT there to be a difference, you can make a distinction between non-syllabified nasals in prenasalized consonants vs. syllabified nasals that precede obstruants--with the phonetic difference being the length of the nasal.
So, for example, [anda] and [an̩da], which would be two- and three- syllable words respectively.