Interesting, what version nopCommerce? Does your SendOrderPaidCustomerNotification method in the WorkFlowMessageService have this line?
_messageTokenProvider.AddCustomerTokens(commonTokens, order.Customer);
In 4.2, I have all of these available:
Allowed message tokens
%Store.Name%, %Store.URL%, %Store.Email%, %Store.CompanyName%, %Store.CompanyAddress%, %Store.CompanyPhoneNumber%, %Store.CompanyVat%, %Facebook.URL%, %Twitter.URL%, %YouTube.URL%, %Customer.Email%, %Customer.Username%, %Customer.FullName%, %Customer.FirstName%, %Customer.LastName%, %Customer.VatNumber%, %Customer.VatNumberStatus%, %Customer.CustomAttributes%, %Customer.PasswordRecoveryURL%, %Customer.AccountActivationURL%, %Customer.EmailRevalidationURL%, %Wishlist.URLForCustomer%, %Order.OrderNumber%, %Order.CustomerFullName%, %Order.CustomerEmail%, %Order.BillingFirstName%, %Order.BillingLastName%, %Order.BillingPhoneNumber%, %Order.BillingEmail%, %Order.BillingFaxNumber%, %Order.BillingCompany%, %Order.BillingAddress1%, %Order.BillingAddress2%, %Order.BillingCity%, %Order.BillingCounty%, %Order.BillingStateProvince%, %Order.BillingZipPostalCode%, %Order.BillingCountry%, %Order.BillingCustomAttributes%, %Order.Shippable%, %Order.ShippingMethod%, %Order.ShippingFirstName%, %Order.ShippingLastName%, %Order.ShippingPhoneNumber%, %Order.ShippingEmail%, %Order.ShippingFaxNumber%, %Order.ShippingCompany%, %Order.ShippingAddress1%, %Order.ShippingAddress2%, %Order.ShippingCity%, %Order.ShippingCounty%, %Order.ShippingStateProvince%, %Order.ShippingZipPostalCode%, %Order.ShippingCountry%, %Order.ShippingCustomAttributes%, %Order.PaymentMethod%, %Order.VatNumber%, %Order.CustomValues%, %Order.Product(s)%, %Order.CreatedOn%, %Order.OrderURLForCustomer%, %Order.PickupInStore%, %Order.OrderId%
For conditional expressions use the token %if (your conditions) ... endif%