It may be that the regulator is bad, yes. It should be able to provide enough power for the Nano to run without issue, especially since you aren’t even loading it yet. It’s also possible that there is a weak connection somewhere and something isn’t making good contact. Silly as it may sound, sometimes these problems can be solved simply by taking it apart and reassembling it, since this requires you to go through every connection over again.
You could put a capacitor across the output of the regulator as well, but this is probably more of a patch-over than an actual resolution to your issue.
Check the inner diameter of your barrel jack as well – there are both 2.5 and 2.1 mm ID jacks available which share the same 5.5 mm outer diameter. The Nano connection is 2.1 mm ID, so a 2.5 mm barrel jack will fit, but not make a good connection.
Unfortunately I’m not sure I’m able to provide much more help than this without being able to look at your Kaya in person.