Can I switch to a new type of bottom bracket? The bottom bracket on my MTB (Cube Analog '17) needs to be replaced, my local bike shop said he didn't have the required piece: a square bottom bracket 115 x 73mm.
Since I can't find this type of bottom bracket online, what are my options?

Can I use a different type of bottom bracket and will that require a change of cranks as well? What's a good choice?
If I purchase a whole new crankset (the original Shimano FC-M3000, 40x30x22T, 175mm), will that include the bottom bracket? Is this hard to install? I found one in a local shop but the specs mention 113mm instead of the 115mm that the shop advised me, I'm guessing this is the length of the bottom bracket and 1mm on each side less won't make a difference?

Thanks for any tips!
my local bike shop said he didn't have the required piece

What? They can't order one? I'd be immediately suspicious and look for another local bike repair shop.
To make sure you order the correct bottom bracket for your crank it's best to look at the Shimano axle length code. The Analog has a Acera FC-M3000 crank. The Shimano square taper bottom bracket axle length code for this crank is 'LL113'. Looking through the Shimano MTB BB specs page we can find that a BB-UN300 has that length code for a 73mm BB shell. Now you know what to look for online (hint).

Can I use a different type of bottom bracket and will that require a change of cranks as well?

Yes and yes. The other choice for a threaded bottom bracket shell (sticking with Shimano) is a HollowTechII external bearings and a 'two-piece' 24mm axle crank. This would be considered an upgrade over the square taper type. You Can pick any Shimano MTB 3x9 HollowTech crank with the same chainring sizes and crank arm length as you have. As an example (product recommendations are off-topic here) the Alivio FC-MT210-3.

If I purchase a whole new crankset .. will that include the bottom bracket?

No. Batteries Bottom brackets sold separately. Shimano two-piece cranks will fit in both a threaded Hollowtech II and BB86/92 press-fit bottom bracket so they do not come with a bottom bracket.

Is this hard to install?

Not really and there are loads of guides online but you need several special tools. To get the square taper cranks off the bottom bracket you need a crank puller. To get the cartridge bottom bracket out of the frame shell you need a tool that fits in the cup splines (there are several variations) and a big wrench or socket driver. To mount HollowTech bottom bracket cups a special wrench is needed. Examples can be seen here. Strictly speaking you need a torque wrench to mount the left crank arm on a Hollowtech crank. You definitely need one to get crank arms mounted on a square taper.
Really, you should be able to get the bike store (or a different one) to order the correct bottom bracket for you. Switching to a Hollowtech crank will be relatively expensive even before the cost of tools. You might look for bicycle co-operatives in your area that will rent out tools or workshop space if you really want to do the upgrade yourself.