Is it fine to use a startup as an affiliation?
I was asked to provide an affiliation [for a paper]. Not providing one is not an option, in the sense it's a mandatory field on the form. 


You could write N/A or unaffiliated, since this seems like the most relevant answer.


  Does it make sense to use [my startup] as my affiliation (which is 100% true though not necessarily relevant)? 


Just like your employer decided that they didn't want their company name on your paper, you should consider whether you want your startup name on your paper. 



On an aside, I wonder whether an employer (generally) has the right to deny an employee of listing the employer as their affiliation. (Some employers -- especially those in R&amp;D -- will explicitly define contractual conditions, but generally they will not.)