The "noDataTemplate" is displayed when there is no data to be shown to satisfy the filter expression. In case of some data the "noDataTemplate" will not be shown at all. Having this in mind such functionality can not be achieved.
As a workaround I would suggest an alternative solution:
1. Use the Kendo UI ComboBox dataBound event to show a button next to the ComboBox on the page (or below the widget).
2. In order to access the DataSource of the ComboBox the dataSource property can be used. The filter method of the DataSource returns the filter information currently applied to the DataSource (if any).
3. The custom button will add a new item to the DataSource as shown in the http://demos.telerik.com/kendo-ui/combobox/addnewitem demo.
Telerik by Progress