К сожалению, нет способа заставить APNS отправить сообщение всем зарегистрированным устройствам для получения уведомлений от вашего приложения, так что да, вы должны сделать это одно за другим.
При 10000 пользователей не должно быть заметной задержки между первым и последним пользователем. Поскольку каждое устройство имеет свое сетевое соединение, уведомления в любом случае обычно задерживаются на несколько сотен миллисекунд.