You could go for a combination of the 2. If some of the messages that are to be delivered are unique to a device, then you should look at using the topic hierarchy to separate the device specific configuration from the common pieces. Scale and device addressing is one of the concerns that the message broker is designed to address.
The key decision you are making is: are my devices completely dumb, or do i want to perform some compute at the edge. I currently see a combination of the 2. If devices are just transmitting data, then they can be relatively dumb. If they are doing 2 way command and control, then they are more intelligent and you need to process more logic on the device.
For Common messages - Fan out is the role of the broker. a publisher (of the configuration) should use a wildcard (device/*) to publish - 1 send, and the broker will take care of managing the delivery to each registered device. Additionally, you can use the device ID as part of your topic hierarchy - adds security and ensures subscribers can only subscribe to their one device topics. In theory the common template should only be sent as part of the device registration process (so could still only be sent to a single device, or if there is a change to the core template (all devices). This is also very common in use cases where you are managing device firmware updates.
Some thoughts on your topics:
Publish to Message is delivered to
device/* All devices
device/$deviceid/ single device
template/* all devices
template/$deviceid/ single device
template/*/new devices registered to receive a new template
You could also have some other topic level to create subsets of devices (based on their version, brand, capabilities, etc). You could even use a date/time topic to be able to address any devices that have registered after a specific date time. e.g. when a device receives the template, it subscribes to a topic device/$deviceid/yyyy/mm/dd your server side logic can then send messages to devices registered on a specific date, or ranges. Alternatively you could have a topic for new devices: device/$deviceid/new and your server side can periodically send a message to device/*/new with the template.
you may also need to take into consideration a device requesting it's configuration (reboot, initial config etc).
feel free to PM me if you want to discuss in more detail.